Pagini recente » Cod sursa (job #1791816) | Cod sursa (job #1171041) | Cod sursa (job #385547) | Cod sursa (job #2874558) | Cod sursa (job #1877352)
#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<<20];
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;
}