Pagini recente » Cod sursa (job #2007975) | Cod sursa (job #185513) | Cod sursa (job #354927) | Cod sursa (job #1728076) | Cod sursa (job #2245843)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
const int DL=1000005;
const int DC=10005;
char tx[DL],c[DC];
int n,pi[DC],lg,lgc;
void p() {
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()
{
lg=strlen(tx+1);
for(int i=1;i<=lg;i++)
f>>tx[i];
for(int k=1; k<=n; ++k) {
f>>c[k];
lgc=strlen(c+1);
int pot=0;
for(int i=0; i<=lgc; ++i) pi[i]=0;
p();
for(int i=1,q=0; i<=lg; ++i) {
for(;q!=0 && tx[i]!=c[q+1]; q=pi[q]);
if(tx[i]==c[q+1]) ++q;
if(q==lgc) ++pot;
}
g<<pot<<"\n";
}
return 0;
}