Cod sursa(job #2409702)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 19 aprilie 2019 12:46:49
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n, m, i;
char a[1000005], s[10005];
struct trie{
    int sum, viz;
    trie *f[26], *bc;
    vector<trie*> w;
    trie(){
        sum = viz = 0;
        bc = NULL;
        for(int i = 0; i < 26; i++){
            f[i] = NULL;
        }
    }
};
trie *r, *nod, *rad[105], *aux;
queue<trie*> c;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
void adauga(trie *r, char *s){
    if(*s == 0){
        rad[i] = r;
    }
    else{
        if(r->f[*s - 'a'] == NULL){
            r->f[*s - 'a'] = new trie;
        }
        adauga(r->f[*s - 'a'], s + 1);
    }
}
void dfs(trie *nod){
    if(nod->viz == 1){
        return;
    }
    nod->viz = 1;
    for(int i = 0; i < nod->w.size(); i++){
        trie *aux = nod->w[i];
        dfs(aux);
        nod->sum += aux->sum;
    }
}
int main(){
    fin>> a + 1;
    m = strlen(a + 1);
    fin>> n;
    r = new trie;
    for(i = 1; i <= n; i++){
        fin>> s;
        adauga(r, s);
    }
    for(i = 0; i < 26; i++){
        if(r->f[i] != NULL){
            r->w.push_back(r->f[i]);
            r->f[i]->bc = r;
            c.push(r->f[i]);
        }
    }
    while(!c.empty()){
        nod = c.front();
        c.pop();
        for(i = 0; i < 26; i++){
            if(nod->f[i] != NULL){
                aux = nod->bc;
                while(aux != r && aux->f[i] == NULL){
                    aux = aux->bc;
                }
                if(aux->f[i] != NULL){
                    nod->f[i]->bc = aux->f[i];
                }
                else{
                    nod->f[i]->bc = r;
                }
                nod->f[i]->bc->w.push_back(nod->f[i]);
                c.push(nod->f[i]);
            }
        }
    }
    nod = r;
    for(i = 1; i <= m; i++){
        a[i] -= 'a';
        while(nod != r && nod->f[ a[i] ] == NULL){
            nod = nod->bc;
        }
        if(nod->f[ a[i] ] != NULL){
            nod = nod->f[ a[i] ];
        }
        nod->sum++;
    }
    dfs(r);
    for(i = 1; i <= n; i++){
        fout<< rad[i]->sum <<"\n";
    }
    return 0;
}