Pagini recente » Cod sursa (job #2644784) | Cod sursa (job #996493) | Cod sursa (job #2849646) | Cod sursa (job #2801537) | Cod sursa (job #1553078)
#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);
}
}