Pagini recente » Cod sursa (job #2735787) | Cod sursa (job #916987) | Cod sursa (job #783308) | Cod sursa (job #2329795) | Cod sursa (job #3180267)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
char txt[1000001],word[10001];
struct Trie
{
Trie *fiu[26],*suffix,*output;
bool ok=false;
int nrap=0;
}*rez[101];
Trie *root=new Trie;
void startup(Trie *nod)
{
for(int i=0;i<26;i++)
nod->fiu[i]=NULL;
}
void out(Trie *nod)
{
if(nod!=root)
{
nod->nrap++;
out(nod->output);
}
}
Trie *suf(Trie *nod, int ch)
{
if(nod->fiu[ch]!=NULL)
return nod->fiu[ch];
else
if(nod!=root)
return suf(nod->suffix,ch);
else
return root;
}
Trie *coada[1000002];
Trie *add(Trie *nod, char *word)
{
if(*word==NULL)
{
nod->ok=true;
return nod;
}
else
{
if(nod->fiu[word[0]-'a']==NULL)
{
nod->fiu[word[0]-'a']=new Trie;
startup(nod->fiu[word[0]-'a']);
}
return add(nod->fiu[word[0]-'a'],word+1);
}
}
int main()
{
int n,i,m;
cin>>txt>>n;
m=strlen(txt);
startup(root);
root->suffix=root;
root->output=root;
for(i=1;i<=n;i++)
{
cin>>word;
rez[i]=add(root,word);
}
int j,t;
for(t=0,j=0;t<26;t++)
if(root->fiu[t]!=NULL)
{
coada[++j]=root->fiu[t];
coada[j]->suffix=root;
}
for(i=1;i<=j;i++)
{
if(coada[i]->suffix->ok==true)
coada[i]->output=coada[i]->suffix;
else
coada[i]->output=coada[i]->suffix->output;
for(t=0;t<26;t++)
if(coada[i]->fiu[t]!=NULL)
{
coada[++j]=coada[i]->fiu[t];
coada[j]->suffix=suf(coada[i]->suffix,t);
}
}
Trie *nodc=root;
int ch;
for(i=0;i<m;i++)
{
ch=txt[i]-'a';
if(nodc->fiu[ch]!=NULL)
nodc=nodc->fiu[ch];
else
{
nodc=nodc->suffix;
while(nodc->fiu[ch]==NULL&&nodc!=root)
nodc=nodc->suffix;
if(nodc->fiu[ch]!=NULL)
nodc=nodc->fiu[ch];
}
nodc->nrap++;
out(nodc->output);
}
for(i=1;i<=n;i++)
cout<<rez[i]->nrap<<'\n';
return 0;
}