Pagini recente » Cod sursa (job #470033) | Cod sursa (job #2048257) | Cod sursa (job #668624) | Cod sursa (job #3200932) | Cod sursa (job #1230624)
#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;
}