Cod sursa(job #1230624)

Utilizator andreey_047Andrei Maxim andreey_047 Data 18 septembrie 2014 17:55:05
Problema Aho-Corasick Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <cstdio>
#define in "ahocorasick.in"
#define out "ahocorasick.out"
#define nmax 1000001
#include <cstring>
using namespace std;
char A[nmax],B[10001];
int t,n,m,pi[nmax],nr;
void pref(){
 int q=0,i;
 for(i = 1; i<=m;i++) pi[i]=0;
 for(i = 2; i <= m; i++){
    while(q && B[q+1] != B[i])
        q = pi[q];
    if(B[q+1] == B[i])
        q++;
    pi[i]=q;
 }
}
int main(){
    int q,i;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    scanf("%s%d",A+1,&t);
    n = strlen(A+1);
    while(t--){
        scanf("%s",B+1);
        m = strlen(B+1);
        q = nr = 0;
        pref();
//        for(i=1;i<=m;i++) cout << pi[i]<<' ';
//        cout << '\n';
        for(i = 1;i<=n;i++){
            while(q && B[q+1] != A[i])
                q=pi[q];
            if(B[q+1] == A[i]) q++;
            if(q == m){
                q = pi[q];
                nr++;
            }
        }
        printf("%d\n",nr);
    }
    return 0;
}