Pagini recente » Cod sursa (job #1340408) | Cod sursa (job #469967) | Cod sursa (job #709237) | Cod sursa (job #1892970) | Cod sursa (job #2281642)
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
int n,i,j;
int v[105],w[105];
char p[10005];
string S,nu;
struct trie
{
int id,ap,n0;
trie *fii[26],*bk;
trie()
{
id=ap=n0=0;
bk=0;
memset(fii, 0, sizeof(fii));
}
} *u,*r,*x;
trie *T=new trie;
deque<trie *> q,b;
void do_trie(trie *t,char *ch)
{
if(*ch=='\0')
{
if(t->id==0) t->id=i;
w[i]=t->id;
t->ap=1;
return;
}
int nh=*ch-'a';
if(t->fii[nh]==0) t->fii[nh]=new trie;
do_trie(t->fii[nh], ch+1);
}
void automata()
{
for(int i=0;i<=25;i++)
if(T->fii[i]!=0)
{
T->fii[i]->bk = T;
q.push_back(T->fii[i]);
}
T->bk=T;
while(!q.empty())
{
r=q.front();
b.push_back(r);
q.pop_front();
for(int i=0;i<=25;i++)
if(r->fii[i]!=0)
{
u=r->fii[i];
x=r->bk;
while(x!=T && x->fii[i]==0)
x=x->bk;
if(x->fii[i]!=0) u->bk=x->fii[i];
else u->bk=T;
q.push_back(u);
}
}
}
void strmatch()
{
x=T;
int ls=(int)S.size();
for(int i=1;i<ls;i++)
{
int ch=S[i]-'a';
while(x!=T && x->fii[ch]==0)
x=x->bk;
if(x->fii[ch]!=0) x=x->fii[ch];
x->n0++;
}
}
int main() {
getline(fin,nu);
S=" "+nu;
fin>>n; getline(fin,nu);
for(i=1;i<=n;i++)
{
fin.getline(p,10005,'\n');
do_trie(T, p);
}
automata();
strmatch();
while(!b.empty())
{
x=b.back();
b.pop_back();
x->bk->n0+=x->n0;
if(v[x->id]==0) v[x->id]=x->n0;
}
for(i=1;i<=n;i++)
fout<<v[w[i]]<<"\n";
}