Pagini recente » Cod sursa (job #169257) | Cod sursa (job #2671861) | Cod sursa (job #838309) | Cod sursa (job #3170973) | Cod sursa (job #1102757)
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#define MAXC 26
#define MAXN 105
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
struct nod{
int nr;
vector<int> cuv;
nod *fiu[MAXC],*fail;
nod(){
int i;
nr=0;
for(i=0;i<MAXC;i++)
fiu[i]=NULL;
fail=NULL;}};
nod *start,*a,*b;
queue<nod *> q;
vector<nod *> aq;
int n,x,sol[MAXN];
string s,s1;
int main()
{
int i,j;
f>>s>>n;
start=new nod;
for(i=1;i<=n;i++){
f>>s1;
a=start;
for(j=0;j<s1.size();j++){
x=s1[j]-'a';
if(a->fiu[x]==NULL)
a->fiu[x]=new nod;
a=a->fiu[x];}
a->cuv.push_back(i);}
start->fail=start;
for(i=0;i<MAXC;i++)
if(start->fiu[i]!=NULL){
start->fiu[i]->fail=start;
q.push(start->fiu[i]);}
while(!q.empty()){
a=q.front();
q.pop();
aq.push_back(a);
for(i=0;i<MAXC;i++){
if(a->fiu[i]==NULL)
continue;
b=a->fail;
while(b!=start&&b->fiu[i]==NULL)
b=b->fail;
if(b->fiu[i]==NULL)
a->fiu[i]->fail=start;
else
a->fiu[i]->fail=b->fiu[i];
q.push(a->fiu[i]);}}
a=start;
for(i=0;i<s.size();i++){
x=s[i]-'a';
while(a!=start&&a->fiu[x]==NULL)
a=a->fail;
if(a->fiu[x]!=NULL)
a=a->fiu[x];
a->nr++;}
for(i=aq.size()-1;i>=0;i--){
a=aq[i];
for(j=0;j<a->cuv.size();j++)
sol[a->cuv[j]]+=a->nr;
a->fail->nr+=a->nr;}
for(i=1;i<=n;i++)
g<<sol[i]<<'\n';
f.close();
g.close();
return 0;
}