Pagini recente » Cod sursa (job #2650479) | Cod sursa (job #479579) | Cod sursa (job #700471) | Cod sursa (job #1923400) | Cod sursa (job #1686017)
#include <bits/stdc++.h>
#define Nmax 1000005
#define pb push_back
using namespace std;
char a[Nmax],s[Nmax];
int n,l;
struct Trie
{
Trie *leg[26],*suf;
int cnt;
bool viz;
vector <Trie*> L;
Trie()
{
for(int i=0;i<26;++i) leg[i]=0;
cnt=0; L.clear(); viz=0;
}
} *rad = new Trie(),*wh[105];
queue <Trie*> Q;
inline void Add(Trie *nod, int p, int ind)
{
if(p==l+1)
{
wh[ind]=nod; return;
}
if(!nod->leg[s[p]-'a']) nod->leg[s[p]-'a']=new Trie();
Add(nod->leg[s[p]-'a'],p+1,ind);
}
inline void Make_Suf()
{
int i;
Trie *nod,*node;
for(i=0;i<26;++i)
if(rad->leg[i])
{
rad->leg[i]->suf=rad;
rad->L.pb(rad->leg[i]);
Q.push(rad->leg[i]);
}
while(!Q.empty())
{
nod=Q.front(); Q.pop();
for(i=0;i<26;++i)
if(nod->leg[i])
{
node=nod->suf;
while(node!=rad && !node->leg[i]) node=node->suf;
if(node->leg[i]) node=node->leg[i];
nod->leg[i]->suf=node;
node->L.pb(nod->leg[i]);
Q.push(nod->leg[i]);
}
}
}
inline void Dfs(Trie *nod)
{
nod->viz=1;
for(auto it : nod->L)
{
if(!it->viz) Dfs(it);
nod->cnt+=it->cnt;
}
}
int main()
{
int m,i;
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
cin>>(a+1)>>m; n=strlen(a+1);
for(i=1;i<=m;++i)
{
cin>>(s+1); l=strlen(s+1);
Add(rad,1,i);
}
Make_Suf();
Trie *nod = rad;
for(i=1;i<=n;++i)
{
while(!nod->leg[a[i]-'a']) nod=nod->suf;
if(nod->leg[a[i]-'a']) nod=nod->leg[a[i]-'a'];
nod->cnt++;
}
for(i=1;i<=m;++i)
{
if(!wh[i]->viz) Dfs(wh[i]);
cout<<wh[i]->cnt<<"\n";
}
return 0;
}