Cod sursa(job #1553078)

Utilizator andru47Stefanescu Andru andru47 Data 19 decembrie 2015 10:55:36
Problema Aho-Corasick Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;
int phia[100005],phib[1000005],len1,len2,n,k;
char s[1000005],a[100005];
inline void PHIb()
{
    int k;
    for (int i = 1; i<=len1; ++i)
    {
        k=phib[i-1];
        while(k>0&&s[i]!=a[k+1])
            k=phia[k];
        if (s[i]==a[k+1])phib[i]=k+1;
        else phib[i]=0;
    }
    return ;
}
int main()
{
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);
    gets(s+1);
    len1=strlen(s+1);
    scanf("%d\n",&n);
    for (int i = 1; i<=n; ++i)
    {
        gets(a+1);
        len2=strlen(a+1);
       // memset(phia,0,sizeof(phia));
        //memset(phib,0,sizeof(phib));
        phia[1]=0;
        for (int j = 2; j<=len2; ++j)
        {
            k=phia[j-1];
            while(k>0&&a[k+1]!=a[j])
                k=phia[k];
            if (a[k+1]==a[j])phia[j]=k+1;
            else phia[j]=0;
        }
        PHIb();
        int sol = 0;
        for (int i = 1; i<=len1; ++i)
        {
            if (phib[i]==len2)++sol;
        }
        printf("%d\n",sol);
    }
}