Pagini recente » Cod sursa (job #341600) | Cod sursa (job #196955) | Cod sursa (job #305156) | Cod sursa (job #687278) | Cod sursa (job #2918750)
#include <bits/stdc++.h>
#define N 10005
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct Trie
{
int cnt;
vector<int>curent;
Trie *fiu[26],*fail;
Trie()
{
cnt=0;fail=0;
memset(fiu,0,sizeof(fiu));
}
};
Trie *T=new Trie;
int sol[N],n;
char text[1000005];
void Adaugare(Trie *T,char *s,int i)
{
if(*s==NULL) {T->curent.push_back(i);return;}
if(!T->fiu[*s-'a']) T->fiu[*s-'a']=new Trie;
Adaugare(T->fiu[*s-'a'],s+1,i);
}
queue<Trie*>q;
stack<Trie*>stv;
void bfs(Trie *T)
{
Trie *p;
T->fail=T;
q.push(T);
while(!q.empty())
{
Trie *u=q.front();
q.pop();
stv.push(u);
for(int i=0;i<26;i++)
if(u->fiu[i])
{
for(p=u->fail;p!=T&&!p->fiu[i];p=p->fail);
if(p->fiu[i]&&p->fiu[i]!=u->fiu[i]) p=p->fiu[i];
u->fiu[i]->fail=p;
q.push(u->fiu[i]);
}
}
T->fail=NULL;
}
void ahoaho(char *s)
{
Trie *p=T;
for(int i=0;s[i];i++)
{
for(;!p->fiu[s[i]-'a']&&p!=T;p=p->fail);
if(p->fiu[s[i]-'a']) p=p->fiu[s[i]-'a'];
p->cnt++;
}
}
void antibfs(Trie *T)
{
while(!stv.empty())
{
Trie *u=stv.top();
stv.pop();
if(u->fail) u->fail->cnt+=u->cnt;
for(int i=0;i<u->curent.size();i++) sol[u->curent[i]]=u->cnt;
}
}
int main()
{
char s[N];
fin>>text;
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>s;
Adaugare(T,s,i);
}
bfs(T);
ahoaho(text);
antibfs(T);
for(int i=1;i<=n;i++) fout<<sol[i]<<"\n";
return 0;
}