Pagini recente » Cod sursa (job #511847) | Cod sursa (job #436544) | Cod sursa (job #1876239) | Cod sursa (job #1680796) | Cod sursa (job #1650358)
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
class Aho_Corasick
{
public:
void add_word(char sir[])
{
int n=strlen(sir),nod=rad;
wordcnt++;
for(int i=0;i<n;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].indcuv.push_back(wordcnt-1);
}
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(v[k].delta[j]!=nil && k!=nod) k=v[k].delta[j];
if(v[nod].delta[j]!=nil)
{
v[v[nod].delta[j]].pi=k;
q.push_back(v[nod].delta[j]);
}
else v[nod].delta[j]=k;
}
}
reverse(q.begin(),q.end());
}
vector<int> getfreq(char sir[])
{
vector<int> freq=vector<int>(wordcnt,0);
int n=strlen(sir),nod=rad;
for(int i=0;i<n;i++)
{
nod=v[nod].delta[cod(sir[i])];
v[nod].nr++;
}
for(vector<int>::iterator it=q.begin();it!=q.end();it++)
if(*it!=rad) v[v[*it].pi].nr+=v[*it].nr;
for(int i=0;i<v.size();i++)
for(vector<int>::iterator it=v[i].indcuv.begin();it!=v[i].indcuv.end();it++) freq[*it]=v[i].nr;
return freq;
}
private:
static const int sigma=26,nil=-1;
struct node
{
int nr,pi;
vector<int> delta,indcuv;
node()
{
nr=pi=0;
delta=vector<int>(sigma,nil);
indcuv=vector<int>();
}
};
vector<node> v=vector<node>(1,node());
vector<int> q;
int rad=0,wordcnt=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.getfreq(sir);
for(int i=0;i<n;i++) printf("%d\n",sol[i]);
return 0;
}