Cod sursa(job #2526402)

Utilizator maria15Maria Dinca maria15 Data 18 ianuarie 2020 16:15:49
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

int n;

struct trie{
    int NrCuv;
    int NrFii;
    int sol;
    trie *sufix;
    trie *Fiu[26];
    vector<trie *> v;
    trie(){
        NrFii = 0;
        sol = 0;
        sufix = NULL;
        for(int i = 0;i<26;i++)
            Fiu[i] = NULL;
        v.clear();
    }
};

trie *rad = new trie, *w[102];
queue<trie *> coada;

trie *adauga(char *s, trie *nod){
    if(*s == 0){
        return nod;
    }
    int lit = *s-'a';
    if(nod->Fiu[lit] == NULL){
        nod->Fiu[lit] = new trie;
        nod->NrFii++;
    }
    return adauga(s+1, nod->Fiu[lit]);
}

void dfs(trie *root){
    for(int i = 0;i<root->v.size();i++){
        trie *vecin = root->v[i];
        dfs(vecin);
        root->sol += vecin->sol;
    }
}

char a[1000002], x[10002];
int i;

int main(){
    fin>>a;
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>x;
        w[i] = adauga(x, rad);
    }
    coada.push(rad);
    while(!coada.empty()){
        trie *p = coada.front();
        coada.pop();
        for(i=0;i<26;i++)
            if(p->Fiu[i]){
                trie *aux = p->sufix;
                while(aux && aux->Fiu[i] == NULL)
                    aux = aux->sufix;
                if(aux == 0)
                    p->Fiu[i]->sufix = rad;
                else
                    p->Fiu[i]->sufix = aux->Fiu[i];
                p->Fiu[i]->sufix->v.push_back(p->Fiu[i]);
                coada.push(p->Fiu[i]);
            }
    }
    trie *crt = rad;
    for(i=0;a[i]!=0;i++){
        int lit = a[i]-'a';
        while(crt && crt->Fiu[lit] == NULL)
            crt = crt->sufix;
        if(crt != 0){
            crt->Fiu[lit]->sol++;
            crt = crt->Fiu[lit];
        }
        else
            crt = rad;
    }
    dfs(rad);
    for(i=1;i<=n;i++)
        fout<<w[i]->sol<<"\n";
    return 0;
}