Cod sursa(job #1115709)

Utilizator PatrikStepan Patrik Patrik Data 21 februarie 2014 23:14:40
Problema Aho-Corasick Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
    #include<cstdio>
    #include<cstring>
    using namespace std;
    #define MAX_A 1000002
    #define MAX_S 10002
    int N , Q, pi[MAX_A] , sol , L;
    char A[MAX_A] , S[MAX_S];

    void prefix();
    void solve();

    int main()
    {
        freopen("ahocorasick.in" , "r" , stdin );
        freopen("ahocorasick.out" , "w" , stdout );
        scanf("%s" , A+1);
        scanf("%d\n" , &Q );
        L = strlen(A+1);
        for(int k = 1; k <= Q ; ++k )
        {
            scanf("%s" , S+1);
            N = strlen(S+1);
            prefix();
            solve();
            printf("%d\n" , sol );
        }
        return 0;
    }

    void prefix()
    {
        int k = 0;
        for(int i = 2 ; i <= N ; ++i )
        {
            while(k && S[i] != S[k+1])
                k = pi[k];
            if(S[i] == S[k+1])
                k++;
            pi[i] = k;
        }
    }

    void solve()
    {
        int l = strlen(S+1) , k = 0;
        sol = 0;
        for(int i =1 ; i <= L ; ++i )
        {
            while(k && A[i] != S[k+1])
                k = pi[k];
            if(A[i] == S[k+1])
                k++;
            if(k == l)sol++;
        }
    }