Pagini recente » Cod sursa (job #2964023) | Borderou de evaluare (job #1004039) | Cod sursa (job #2115862) | Cod sursa (job #2772304) | Cod sursa (job #2393413)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct trie
{
trie *child[26];
trie *fail;
int val;
int ap;
trie()
{
for(int i=0;i<26;i++)child[i]=0;
fail=0;
val=0;
ap=0;
}
};
trie *root=new trie();
trie *q[1000005];
trie *lst[1000005];
trie *ending[105];
int n,k,l,ans,length;
string sir;
string t;
void add(int it)
{
trie *where=root;
k=t.size();
for(int i=0;i<k;i++)
{
if(where->child[t[i]-'a']==0)
{
where->child[t[i]-'a']=new trie();
where->child[t[i]-'a']->val=t[i]-'a';
}
where=where->child[t[i]-'a'];
}
ending[it]=where;
}
void find_fail()
{
root->fail=root;
q[0]=root;
lst[0]=root;
length=1;
int where=0;
while(where<length)
{
trie *pos=q[where];
trie *last=lst[where];
where++;
last=last->fail;
int v=pos->val;
while(last!=root && last->child[v]==0)
last=last->fail;
if(last==root)
{
if(last->child[v]!=0 && pos!=root && pos!=last->child[v])
pos->fail=last->child[v];
else
pos->fail=root;
}
else
pos->fail=last->child[v];
for(int i=0;i<='z'-'a';i++)
if(pos->child[i]!=0)
{
q[length]=pos->child[i];
lst[length]=pos;
length++;
}
}
}
void solve()
{
trie *where;
for(int i=length-1;i>0;i--)
{
where=q[i];
if(where->fail!=root)
(where->fail)->ap+=where->ap;
}
}
int main()
{
fin>>sir;
fin>>n;
for(int it=1;it<=n;it++)
{
fin>>t;
add(it);
}
find_fail();
trie *where=root;
for(int i=0;i<sir.size();i++)
{
while(where!=root && where->child[sir[i]-'a']==0)
where=where->fail;
if(where->child[sir[i]-'a']!=0)
where=where->child[sir[i]-'a'];
where->ap++;
}
solve();
for(int i=1;i<=n;i++)
fout<<ending[i]->ap<<"\n";
return 0;
}