Cod sursa(job #1569715)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 15 ianuarie 2016 21:01:05
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;
const long long LLINF = 1LL << 62;
const int mod = 1000000007;

struct Trie
{
    Trie *phi, *son[26];
    int cnt;

    Trie()
    {
        memset(son, 0, sizeof(son));
        phi = 0;
        cnt = 0;
    }
} *R, *nod, *phi;

int n, i, j, nr;
int lsir, ls[105];

char sir[1000005];
char s[102][10005];

Trie *q[1000005];

void DFS(Trie *nod)
{
    for(int i = 0; i <= 25; i++)
        if(nod -> son[i])
            DFS(nod -> son[i]);
    nod -> phi -> cnt += nod -> cnt;
}

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

    gets(sir + 1);
    lsir = strlen(sir + 1);

    R = new Trie;
    R -> phi = R;

    scanf("%d\n", &n);
    for(i = 1; i <= n; i++)
    {
        gets(s[i] + 1);
        ls[i] = strlen(s[i] + 1);

        nod = R;
        for(j = 1; j <= ls[i]; j++)
        {
            if(nod -> son[ s[i][j] - 'a' ] == 0)
                nod -> son[ s[i][j] - 'a' ] = new Trie;
            nod = nod -> son[ s[i][j] - 'a' ];
        }
    }

    q[1] = R;
    nr = 1;
    for(j = 1; j <= nr; j++)
    {
        nod = q[j];

        for(i = 0; i <= 25; i++)
            if(nod -> son[i])
            {
                q[++nr] = nod -> son[i];
                if(nod == R)
                {
                    nod -> son[i] -> phi = R;
                    continue;
                }

                phi = nod -> phi;
                while(phi != R && !phi -> son[i])
                    phi = phi -> phi;
                if(phi -> son[i])
                    phi = phi -> son[i];
                nod -> son[i] -> phi = phi;
            }
    }

    nod = R;
    for(i = 1; i <= lsir; i++)
    {
        while(nod != R && !nod -> son[ sir[i] - 'a' ])
            nod = nod -> phi;
        if(nod -> son[ sir[i] - 'a' ])
            nod = nod -> son[ sir[i] - 'a' ];
        nod -> cnt++;
    }

    for(i = nr; i >= 1; i--)
        q[i] -> phi -> cnt += q[i] -> cnt;

    for(i = 1; i <= n; i++)
    {
        nod = R;
        for(j = 1; j <= ls[i]; j++)
            nod = nod -> son[ s[i][j] - 'a' ];
        printf("%d\n", nod -> cnt);
    }

    return 0;
}