Cod sursa(job #1333555)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 3 februarie 2015 12:32:52
Problema Aho-Corasick Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#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";
}