Pagini recente » Cod sursa (job #2927824) | Cod sursa (job #826352) | Cod sursa (job #2931953) | Cod sursa (job #902201) | Cod sursa (job #2927728)
#include <bits/stdc++.h>
#define Aho_Corasick AC
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
const int DIM=10005,Alphabet=26;
int n,hmax=0,Answer[DIM/100+1];
char txt[100*DIM],c[DIM];
struct Aho_Corasick
{
vector<int>nodes;
int n0;
Aho_Corasick *Edge[Alphabet],*Fail;
Aho_Corasick()
{
n0=0;
Fail=NULL;
memset(Edge,NULL,sizeof(Edge));
}
} *r;
void Insert(AC *Node,char *p,int i)
{
if(!isalpha(*p))
{
Node->nodes.push_back(i);
return;
}
int nxt=*p-'a';
if(Node->Edge[nxt]==NULL) Node->Edge[nxt]=new AC;
Insert(Node->Edge[nxt],p+1,i);
}
void Bfs(AC *Root)
{
AC *Auxiliary;
Root->Fail=Root;
queue<AC*>q;
q.push(Root);
while(!q.empty())
{
AC *Node = q.front();
q.pop();
for(int i=0; i<Alphabet; i++)
if(Node->Edge[i]!=NULL)
{
for(Auxiliary=Node->Fail; Auxiliary!=Root && Auxiliary->Edge[i]==NULL; Auxiliary=Auxiliary->Fail);
if(Auxiliary->Edge[i]!=NULL && Auxiliary->Edge[i]!=Node->Edge[i]) Auxiliary=Auxiliary->Edge[i];
Node->Edge[i]->Fail=Auxiliary;
q.push(Node->Edge[i]);
}
}
Root->Fail=NULL;
}
void Bfss(AC *Root)
{
queue< pair<AC*,int> >q;
vector< AC* > levels[hmax+1] ;
q.push({Root,0});
while(!q.empty())
{
AC *Node = q.front().first;
int h=q.front().second;
levels[h].push_back(Node);
q.pop();
for(int i=0; i<Alphabet; i++)
{
if(Node->Edge[i]!=NULL)
{
q.push({Node->Edge[i],h+1});
}
}
}
for(int i=hmax; i>=1; i--)
{
for(int j=0; j<levels[i].size(); j++)
{
AC* Node = levels[i][j];
Node->Fail->n0 += Node->n0;
for(int z=0; z<Node->nodes.size(); z++) Answer[Node->nodes[z]]=Node->n0;
}
}
}
int main()
{
f>>txt;
f>>n;
r=new Aho_Corasick;
for(int i=1; i<=n; i++)
{
f>>c;
hmax=max(hmax,(int)strlen(c));
Insert(r,c,i);
}
Bfs(r);
AC* p = r;
int l=strlen(txt);
for(int i=0; i<l; i++)
{
int nxt=txt[i]-'a';
for(; p->Edge[nxt]==NULL&&p!=r; p=p->Fail);
if(p->Edge[nxt]!=NULL) p=p->Edge[nxt];
++p->n0;
}
Bfss(r);
for(int i=1; i<=n; i++) g<<Answer[i]<<'\n';
return 0;
}