Cod sursa(job #1877354)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 13 februarie 2017 11:42:44
Problema Aho-Corasick Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
using namespace std;
int i,j,n,l,x,k,m,S[1<<20];
char a[1<<20];
struct trie
{
    int nr,Son[26];
}T[1<<19];
vector <int> Sol;
int main()
{
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);
    gets(a);
    for(i=0;a[i]>='a'&&a[i]<='z';++i) S[++n]=a[i]-'a';
    scanf("%d\n",&m);
    for(j=1;j<=m;++j)
    {
        gets(a);
        int l=strlen(a);
        for(i=x=0;i<l;++i)
        {
            int y=a[i]-'a';
            if(!T[x].Son[y])
            {
                T[x].Son[y]=++k;
                x=k;
            }
            else x=T[x].Son[y];
        }
        Sol.push_back(x);
    }
    for(i=1;i<=n;++i)
        for(j=i,x=0;j<=n;++j)
        {
            if(!T[x].Son[S[j]]) break;
            x=T[x].Son[S[j]];
            T[x].nr++;
        }
    for(j=0;j<m;++j) printf("%d\n",T[Sol[j]].nr);
    return 0;
}