Pagini recente » Cod sursa (job #418641) | Cod sursa (job #873960) | Cod sursa (job #369346) | Cod sursa (job #1865991) | Cod sursa (job #1115709)
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX_A 1000002
#define MAX_S 10002
int N , Q, pi[MAX_A] , sol , L;
char A[MAX_A] , S[MAX_S];
void prefix();
void solve();
int main()
{
freopen("ahocorasick.in" , "r" , stdin );
freopen("ahocorasick.out" , "w" , stdout );
scanf("%s" , A+1);
scanf("%d\n" , &Q );
L = strlen(A+1);
for(int k = 1; k <= Q ; ++k )
{
scanf("%s" , S+1);
N = strlen(S+1);
prefix();
solve();
printf("%d\n" , sol );
}
return 0;
}
void prefix()
{
int k = 0;
for(int i = 2 ; i <= N ; ++i )
{
while(k && S[i] != S[k+1])
k = pi[k];
if(S[i] == S[k+1])
k++;
pi[i] = k;
}
}
void solve()
{
int l = strlen(S+1) , k = 0;
sol = 0;
for(int i =1 ; i <= L ; ++i )
{
while(k && A[i] != S[k+1])
k = pi[k];
if(A[i] == S[k+1])
k++;
if(k == l)sol++;
}
}