Cod sursa(job #2334247)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 2 februarie 2019 13:42:45
Problema Aho-Corasick Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 2.04 kb
# include <fstream>
# include <cstring>
# include <queue>
# include <vector>
# define DIMA 1000010
# define DIMB 10010
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct trie{
    int val,sol;
    vector<trie *> v;
    trie *nx[26],*back;
    trie(){
        val=sol=0;
        back=NULL;
        for(int i=0;i<26;i++)
            nx[i]=NULL;
    }
} *tata,*nc,*nv,*prefix;
queue<trie *> q;
char b[105][DIMB],a[DIMA];
int n,m,i,r;
void adauga(trie *nod, char *s){
    if(*s==NULL)
        return;
    if(nod->nx[*s-'a']==NULL)
        nod->nx[*s-'a']=new trie;
    adauga(nod->nx[*s-'a'],s+1);
}
int solutie(trie *nod,char *s){
    if(*s==NULL)
        return nod->sol;
    return solutie(nod->nx[*s-'a'],s+1);
}
void dfs(trie *nod){
    for(int i=0;i<nod->v.size();i++){
        trie *nv;
        nv=nod->v[i];
        dfs(nv);
        nod->sol+=nv->sol;
    }
}
int main () {
    tata=new trie;
    fin>>a>>n;
    m=strlen(a);
    for(i=1;i<=n;i++){
        fin>>b[i];
        adauga(tata,b[i]);
    }
    q.push(tata);
    while(!q.empty()){
        r++;
        nc=q.front();
        nc->val=r;
        q.pop();
        for(i=0;i<26;i++){
            nv=nc->nx[i];
            if(nv==NULL)
                continue;
            q.push(nv);
            prefix=nc->back;
            while(prefix!=NULL&&prefix->nx[i]==NULL)
                prefix=prefix->back;
            if(prefix==NULL){
                prefix=tata;
            }
            else{
                if(prefix->nx[i]!=NULL)
                    prefix=prefix->nx[i];
            }
            nv->back=prefix;
            prefix->v.push_back(nv);
        }
    }
    prefix=tata;
    for(i=0;i<m;i++){
        while(prefix!=tata&&prefix->nx[a[i]-'a']==NULL)
            prefix=prefix->back;
        if(prefix->nx[a[i]-'a']!=NULL)
            prefix=prefix->nx[a[i]-'a'];
        prefix->sol++;
    }
    dfs(tata);
    for(i=1;i<=n;i++)
        fout<<solutie(tata,b[i])<<"\n";
    return 0;
}