Cod sursa(job #923508)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 23 martie 2013 17:34:07
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.62 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
using namespace std;

const int dimsir = 1000005, dimcuv = 10005, nrcuvmax = 105;
int N, NR[nrcuvmax];
char A[dimsir], C[nrcuvmax][dimcuv], *PC;

struct nod {
    nod *letter[26], *suffix;
    vector <int> index;
    int value;
    nod () {
        value = 0;
        suffix = NULL;
        //for (int i = 0; i < 26; i++) letter[i] = NULL;
        memset (letter, NULL, sizeof(letter));
    }
} *R;
vector < nod* > Q;

void insert_trie (nod *&n, int i)
{
    if (*PC == '\n' || *PC == 0)
    {
        n->index.push_back (i);
        return;
    }
    char c = *PC - 'a';
    if (n->letter[c] == NULL)
    {
        n->letter[c] = new nod;
    }
    PC ++;
    insert_trie (n->letter[c], i);
}

void cit ()
{
    R = new nod;
    scanf ("%s\n%d\n", A, &N);

    for (int i = 1; i <= N; i++)
    {
        scanf ("%s", C[i]);
        PC = C[i];
        insert_trie (R, i);
    }
}

void bfs1 ()
{
    int i, p = 0;
    nod *n, *suffix;
    for (i = 0; i < 26; i++)
    {
        if (R->letter[i] != NULL)
        {
            Q.push_back (R->letter[i]);
            R->letter[i]->suffix = R;
        }
    }
    R->suffix = R;

    while (p < Q.size ())
    {
        n = Q[p];
        for (i = 0; i < 26; i++)
            if (n->letter[i] != NULL)
            {
                Q.push_back (n->letter[i]);
                for (suffix = n->suffix; suffix != R && suffix->letter[i] == NULL; suffix = suffix->suffix);
                if (suffix->letter[i] != NULL)
                    n->letter[i]->suffix = suffix->letter[i];
                else
                    n->letter[i]->suffix = R;
            }
        p++;
    }
}

void rez ()
{
    nod *n = R; char c;
    for (int i = 0; A[i] && A[i] != '\n'; i++)
    {
        for (c = A[i] - 'a'; n != R && n->letter[c] == NULL; n = n->suffix);
        if (n->letter[c] != NULL) n = n->letter[c];
        n->value ++;
    }
}

void bfs2 ()
{
    nod *n;
    while (!Q.empty())
    {
        n = Q.back ();
        Q.pop_back ();

        n->suffix->value += n->value;
        while (!n->index.empty())
        {
            NR[n->index.back()] = n->value;
            n->index.pop_back ();
        }

        delete n;
    }
}

void afi ()
{
    for (int i = 1; i <= N; i++)
        printf ("%d\n", NR[i]);
}

int main ()
{
    freopen ("ahocorasick.in", "r", stdin);
    freopen ("ahocorasick.out", "w", stdout);

    cit ();
    bfs1 ();
    rez ();
    bfs2 ();
    afi ();

    return 0;
}