Cod sursa(job #1568403)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 14 ianuarie 2016 10:51:39
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include<fstream>
#include<vector>
#include<cstring>
#include<deque>
using namespace std;
int n, i, m;
char a[1000005], s[10005];
struct trie{
    int nr;
    trie *v[26];
    trie *back;
    vector<trie*> w;
    trie(){
        nr = 0;
        w.clear();
        back = NULL;
        for(int i = 0; i < 26; i++){
            v[i] = NULL;
        }
    }
};
trie *p, *f[105], *nod, *aux;
deque<trie*> c;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
trie *adauga(char *s, trie *r){
    if(*s == 0){
        return r;
    }
    else{
        if(r->v[*s - 'a'] == NULL){
            r->v[*s - 'a'] = new trie;
        }
        return adauga(s + 1, r->v[*s - 'a']);
    }
}
void dfs(trie *nod){
    for(int i = 0; i < nod->w.size(); i++){
        dfs(nod->w[i]);
        nod->nr += nod->w[i]->nr;
    }
}
int main(){
    p = new trie;
    fin>> a;
    fin>> n;
    for(i = 1; i <= n; i++){
        fin>> s;
        f[i] = adauga(s, p);
    }
    c.push_back(p);
    while(!c.empty()){
        nod = c.front();
        c.pop_front();
        for(i = 0; i < 26; i++){
            if(nod->v[i] != NULL){
                aux = nod->back;
                while(aux != NULL && aux->v[i] == NULL){
                    aux = aux->back;
                }
                if(aux == 0){
                    nod->v[i]->back = p;
                }
                else{
                    nod->v[i]->back = aux->v[i];
                }
                nod->v[i]->back->w.push_back(nod->v[i]);
                c.push_back(nod->v[i]);
            }
        }
    }
    m = strlen(a);
    aux = p;
    for(i = 0; i < m; i++){
        while(aux != NULL && aux->v[a[i] - 'a'] == NULL){
            aux = aux->back;
        }
        if(aux == NULL){
            aux = p;
        }
        else{
            aux->v[a[i] - 'a']->nr++;
            aux = aux->v[a[i] - 'a'];
        }
    }
    dfs(p);
    for(i = 1; i <= n; i++){
        fout<< f[i]->nr <<"\n";
    }
    return 0;
}