Pagini recente » Cod sursa (job #1380858) | Cod sursa (job #1131591) | Cod sursa (job #1342836) | Cod sursa (job #1528624) | Cod sursa (job #1333555)
#include<fstream>
#include<string>
#include<vector>
using namespace std;
ifstream f("ahocorasick.in");
ofstream o("ahocorasick.out");
struct trie{
trie* f,*fii[26];
vector <int> v;
int nr;
trie(){
f = NULL;
nr=0;
for(int i=0;i<=25;i++)fii[i]=NULL;
}
};
trie *t = new trie, *c[109];
int sum[102];
void ins(string s,trie* t,int x,int y){
if(s.size()==x){t->v.push_back(y);return;}
if(t->fii[s[x]-'a']==NULL)t->fii[s[x]-'a']=new trie;
ins(s,t->fii[s[x]-'a'],x+1,y);
}
int main(){
int n;
string s,text;
f>>text>>n;
for(int i=1;i<=n;i++)f>>s, ins(s,t,0,i);
int in=0,sf=0;t->f=t;c[in]=t;
trie* nod,*f;
while(in<=sf){
nod = c[in];
for(int i=0;i<=25;i++)
if(nod->fii[i]!=NULL){
for(f=nod->f;f->fii[i]==NULL && f!=t;f=f->f);
if(nod->fii[i]!=f->fii[i]&&f->fii[i]!=NULL)f=f->fii[i];
nod->fii[i]->f=f;
c[++sf]=nod->fii[i];
}
in++;
}
t->f=NULL;
trie* p = t;
for(int i=0;i<text.size();i++){
for(;p->fii[text[i]-'a']==NULL && p!=t;p=p->f);
if(p->fii[text[i]-'a']!=NULL)p=p->fii[text[i]-'a'];
p->nr++;
}
for(in--;in>=0;in--){
p = c[in];
if(p->f!=NULL)p->f->nr+=p->nr;
for(int i=0;i<p->v.size();i++)sum[p->v[i]]=p->nr;
}
for(int i=1;i<=n;i++)o<<sum[i]<<"\n";
}