Pagini recente » Cod sursa (job #103) | Cod sursa (job #1588242) | Cod sursa (job #1286855) | Cod sursa (job #1740415) | Cod sursa (job #2344030)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream si("ahocorasick.in");
ofstream so("ahocorasick.out");
int sol[105];
string s,c;
struct trie{
trie *f[26],*fail;
int val;
vector<int> poz;
trie()
{
memset(f,0,sizeof(f));
fail=NULL;
val=0;
}
}*t;
void add(int x)
{
trie *nod=t;
for(int i=0;i<c.size();++i)
{
if(nod->f[c[i]-'a']==NULL)
{
nod->f[c[i]-'a']=new trie();
}
nod=nod->f[c[i]-'a'];
}
nod->poz.push_back(x);
}
vector<trie*> v;
void bfs()
{
trie *nod;
v.push_back(t);
t->fail=t;
for(int i=0;i<v.size();++i)
{
for(int j=0;j<26;++j)
{
if(v[i]->f[j]!=NULL)
{
nod=v[i]->fail;
while(nod->f[j]==NULL&&nod!=t)
{
nod=nod->fail;
}
if(nod->f[j]!=NULL&&nod->f[j]!=v[i]->f[j])
{
nod=nod->f[j];
}
v[i]->f[j]->fail=nod;
v.push_back(v[i]->f[j]);
}
}
}
}
void bfs2()
{
for(int i=v.size()-1;i>=0;--i)
{
if(v[i]->fail!=NULL)
{
v[i]->fail->val+=v[i]->val;
}
for(int j=0;j<v[i]->poz.size();++j)
{
sol[v[i]->poz[j]]+=v[i]->val;
}
}
}
int main()
{
int n;
si>>s;
si>>n;
t=new trie();
for(int i=1;i<=n;++i)
{
si>>c;
add(i);
}
bfs();
trie *nod=t;
for(int i=0;i<s.size();++i)
{
while(nod->f[s[i]-'a']==NULL&&nod!=t)
{
nod=nod->fail;
}
if(nod->f[s[i]-'a']!=NULL)
nod=nod->f[s[i]-'a'];
nod->val++;
}
bfs2();
for(int i=1;i<=n;++i)
so<<sol[i]<<'\n';
return 0;
}