Pagini recente » Cod sursa (job #543140) | Cod sursa (job #832047) | Cod sursa (job #817189) | Cod sursa (job #1169622) | Cod sursa (job #2124163)
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#include <cctype>
#define maxD 1000001
#define maxN 101
#define maxC 10000
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
char H[maxD],s[maxC+2];
int n,Ap[maxN],i;
struct AC
{
vector<int> Ou;
AC *Fiu[26],*Fail;
AC()
{
Fail=NULL;
memset(Fiu,0,sizeof(Fiu));
}
}*t,*Q[maxN*maxN+1];
void ins(AC *node,char *p,int i)
{
if(!isalpha(*p))
{
node->Ou.push_back(i);
return ;
}
else
{
int ch=*p-'a';
if(0==node->Fiu[ch]) node->Fiu[ch]=new AC;
ins(node->Fiu[ch],p+1,i);
}
}
void bfs(AC *nod)
{
int r,l=r=1,j;
Q[1]=nod;
nod->Fail=nod;
while(l<=r)
{
nod=Q[l];
for(i=0;i<=25;i++)
{
if(nod->Fiu[i]==0) continue;
Q[++r]=nod->Fiu[i];
AC *f=nod->Fail;
while(f!=t)
{
if(f->Fiu[i]) break;
else f=f->Fail;
}
if(f->Fiu[i]&&f->Fiu[i]!=nod->Fiu[i])
{
nod->Fiu[i]->Fail=f->Fiu[i];
for(j=0;j<f->Fiu[i]->Ou.size();j++)
{
nod->Fiu[i]->Ou.push_back(f->Fiu[i]->Ou[j]);
}
}
else nod->Fiu[i]->Fail=t;
}
l++;
}
}
int main()
{
f>>H>>n; f.get();
t=new AC;
for(i=1;i<=n;i++)
{
f.getline(s,maxC+1);
ins(t,s,i);
}
bfs(t);
AC *nod=t,*nod2;
i=0;
int len=strlen(H);
for(i=0;i<len;i++)
{
int ch=H[i]-'a';
nod2=nod;
while(nod2!=t)
{
if(nod2->Fiu[ch]) break;
nod2=nod2->Fail;
}
if(nod2->Fiu[ch])
{
nod=nod2->Fiu[ch];
for(int j=0;j<nod->Ou.size();j++)
{
Ap[nod->Ou[j]]++;
}
}
else nod=t;
}
for(i=1;i<=n;i++) g<<Ap[i]<<'\n';
return 0;
}