Pagini recente » Cod sursa (job #2434767) | Cod sursa (job #2963570) | Cod sursa (job #582657) | Cod sursa (job #561252) | Cod sursa (job #1689589)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
class aho_corasick
{
public:
void add_word(char sir[])
{
int lim=strlen(sir),nod=rad;
for(int i=0;i<lim;i++)
{
if(v[nod].delta[cod(sir[i])]==nil) v[nod].delta[cod(sir[i])]=newnode();
nod=v[nod].delta[cod(sir[i])];
}
v[nod].words.push_back(cnt++);
}
void compute_delta_pi()
{
v[rad].pi=rad;
q.push_back(rad);
for(int i=0;i<q.size();i++)
{
int nod=q[i];
for(int j=0;j<sigma;j++)
{
int k=v[nod].pi;
while(k!=rad && v[k].delta[j]==nil) k=v[k].pi;
if(k!=nod && v[k].delta[j]!=nil) k=v[k].delta[j];
if(v[nod].delta[j]==nil) v[nod].delta[j]=k;
else
{
v[v[nod].delta[j]].pi=k;
q.push_back(v[nod].delta[j]);
}
}
}
reverse(q.begin(),q.end());
}
vector<int> get_freq(char sir[])
{
vector<int> freq=vector<int>(cnt,0);
int lim=strlen(sir),nod=rad;
for(int i=0;i<lim;i++)
{
nod=v[nod].delta[cod(sir[i])];
v[nod].sum++;
}
for(vector<int>::iterator it=q.begin();it!=q.end();it++)
if(*it!=rad) v[v[*it].pi].sum+=v[*it].sum;
for(int i=0;i<v.size();i++)
for(vector<int>::iterator it=v[i].words.begin();it!=v[i].words.end();it++)
freq[*it]+=v[i].sum;
return freq;
}
private:
static const int nil=-1,sigma=26;
struct node
{
int pi,sum;
vector<int> delta,words;
node()
{
delta=vector<int>(sigma,nil);
sum=pi=0;
}
};
vector<node> v=vector<node>(1,node());
vector<int> q;
int rad=0,cnt=0;
int cod(char c)
{
return c-'a';
}
int newnode()
{
v.push_back(node());
return v.size()-1;
}
}v;
char sir[1000010],sir1[10010];
int main()
{
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
int n;
scanf("%s\n%d",sir,&n);
for(int i=1;i<=n;i++)
{
scanf("\n%s",sir1);
v.add_word(sir1);
}
v.compute_delta_pi();
vector<int> sol=v.get_freq(sir);
for(int i=0;i<n;i++) printf("%d\n",sol[i]);
}