Pagini recente » Cod sursa (job #2268955) | Cod sursa (job #1023041) | Cod sursa (job #1078895) | Cod sursa (job #438485) | Cod sursa (job #1862118)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int www;
struct Trie
{
vector<int> strings;
int ap;
Trie *son[26],*fail;
Trie()
{
fail=0;ap=0;
for(www=0;www<26;www++)
son[www]=0;
}
}*rad=new Trie,*q[100005],*node,*pi;
string a,s;
int n,ind,i,j,p,u,wh;
int ans[105];
void ins(Trie *node)
{
for(ind=0;ind<a.size();ind++)
{
wh=a[ind]-'a';
if(node->son[wh]==0)
node->son[wh]=new Trie;
node=node->son[wh];
}
node->strings.push_back(i);
}
void calc_suffix()
{
q[1]=rad;p=1;u=1;
rad->fail=rad;
while(p<=u)
{
node=q[p];p++;
for(i=0;i<26;i++)
if(node->son[i]!=0)
{
pi=node->fail;
while(pi!=rad&&pi->son[i]==0)
{
pi=pi->fail;
}
if(pi->son[i]!=0&&pi!=node)pi=pi->son[i];
node->son[i]->fail=pi;
u++;q[u]=node->son[i];
}
}
}
void match()
{
node=rad;
for(i=0;i<s.size();i++)
{
wh=s[i]-'a';
while(node!=rad&&node->son[wh]==0)
node=node->fail;
if(node->son[wh]!=0)
node=node->son[wh];
node->ap++;
}
}
void propag()
{
for(i=u;i>=1;i--)
{
node=q[i];
node->fail->ap+=node->ap;
for(j=0;j<node->strings.size();j++)
ans[node->strings[j]]=node->ap;
}
}
int main()
{
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
f>>s;
f>>n;
for(i=1;i<=n;i++)
{
f>>a;
ins(rad);
}
calc_suffix();
match();
propag();
for(i=1;i<=n;i++)
g<<ans[i]<<'\n';
return 0;
}