Pagini recente » Cod sursa (job #1493411) | Cod sursa (job #1652763) | Cod sursa (job #604151) | Cod sursa (job #2308460) | Cod sursa (job #1316771)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("ahocorasick.in") ;
ofstream g("ahocorasick.out") ;
char T[1000002] ;
char P[10005],c ;
int L[10005] ;
int m,n,k,ct ;
int KMP()
{
int p,t ;
ct=0 ;
k=0 ;
L[1]=0 ;L[2]=0 ;
for(p=2;p<=m;p++)
{
while(k>0&&P[k]!=P[p-1])
k=L[k] ;
if(P[k]==P[p-1])
k++ ;
L[p]=k ;
}
k=0 ;
for(t=1;t<=n;t++)
{
while(k>0&&P[k]!=T[t-1])
k=L[k] ;
if(P[k]==T[t-1])
k++ ;
if(k==m)
{
ct++ ;
//g<<t-m+1<<'\n';
k=L[k] ;
}
}
g<<ct<<'\n' ;
}
int main()
{
int p,t,x,i ;
f.getline(T,sizeof(T)) ;
n=strlen(T) ;
f>>x ;f.get() ;
for(i=1;i<=x;i++)
{
f.getline(P,sizeof(P)) ;
m=strlen(P) ;
KMP() ;
}
return 0;
}