Pagini recente » Cod sursa (job #2693277) | Cod sursa (job #1315618) | Cod sursa (job #1238848) | Cod sursa (job #263679) | Cod sursa (job #2494751)
#include <bits/stdc++.h>
#define DL 1000005
#define DC 10005
using namespace std;
char txt[DL], c[DC];
int n, pi[DC], lg, lgc;
void kmp()
{
for(int i = 2, q = 0; i <= lgc; i++)
{
for(; q != 0 && c[i] != c[q + 1]; q = pi[q]);
if(c[i] == c[q + 1]) q++;
pi[i] = q;
}
}
int main()
{
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
cin >> txt + 1 >> n;
lg = strlen(txt + 1);
for(int k = 1; k <= n; k++)
{
cin >> c + 1;
lgc = strlen(c + 1);
int pot = 0;
for(int i = 0; i <= lgc; i++) pi[i] = 0;
kmp();
for(int i = 1, q = 0; i <= lg; i++)
{
for(; q != 0 && txt[i] != c[q + 1]; q = pi[q]);
if(txt[i] == c[q + 1]) q++;
if(q == lgc) pot++;
}
cout << pot << endl;
}
return 0;
}