Pagini recente » Cod sursa (job #3120935) | Cod sursa (job #1788660) | Cod sursa (job #1645818) | Cod sursa (job #1830742) | Cod sursa (job #1235074)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
#define alpha 26
struct ac{
vector<int> v;
int val;
ac *fiu[alpha], *fail;
ac(){
val=0;
memset(fiu, 0, sizeof(fiu));
fail=0;
}
}*q[1000002];
ac *t;
void ins(ac *nod, char* s, int i)
{
if(!s[0])
{
nod->v.push_back(i);
return;
}
int son=s[0]-'a';
if(!nod->fiu[son])
nod->fiu[son]= new ac;
ins(nod->fiu[son], s+1, i);
}
int st, dr;
void bfs()
{
ac *fail;
st=dr=1;
t->fail=t;
q[1]=t;
while(st<=dr)
{
ac *nod=q[st];
st++;
for(int i=0;i<26;i++)
{
if(!nod->fiu[i])
continue;
fail=nod->fail;
while(fail!=t && !fail->fiu[i])
fail=fail->fail;
if(fail->fiu[i] && fail->fiu[i]!=nod->fiu[i])
fail=fail->fiu[i];
nod->fiu[i]->fail=fail;
q[++dr]=nod->fiu[i];
}
}
t->fail=0;
}
char a[1000002];
char b[10002];
void compute()
{
int i;
ac* nod=t;
for(i=0;a[i];i++)
{
while(nod!=t && !nod->fiu[a[i]-'a'])
{
nod=nod->fail;
}
if(nod->fiu[a[i]-'a'])
nod=nod->fiu[a[i]-'a'];
nod->val++;
}
}
int rez[102];
void antibfs()
{
for(int i=dr;i>0;i--)
{
ac *nod=q[i];
if(q[i]->fail)
q[i]->fail->val+=q[i]->val;
for(vector<int> :: iterator it=nod->v.begin();it!=nod->v.end();it++)
{
rez[*it]=q[i]->val;
}
}
}
int main()
{
int m, i;
t=new ac;
fin >> a;
fin >> m;
for(i=1; i<=m; i++)
{
fin>>b;
ins(t, b, i);
}
bfs();
compute();
//return 0;
antibfs();
for(i=1;i<=m;i++)
{
fout<<rez[i]<<"\n";
}
}