Cod sursa(job #1221088)

Utilizator mariusn01Marius Nicoli mariusn01 Data 19 august 2014 13:38:06
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <fstream>
#include <iostream>
#include <vector>
#define fiu f[*s-'a']
#include <queue>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

struct trie {
    int sol;
    trie *f[26];
    trie *back;
    vector<trie *> v;
    trie() {
        sol = 0;
        for (int i=0;i<26;i++)
            f[i] = 0;
        back = 0;
        v.clear();
    }
};

trie *root = new trie();

char A[1000100], s[10010];
trie *w[101], *nod, *aux;
queue<trie *> Q;
int n;

trie *adauga(trie *r, char *s) {
    if (*s == 0) {
        return r;
    }
    if (r->fiu == NULL) {
        r->fiu = new trie;
    }
    return adauga (r->fiu, s+1);
}

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

}

int main(){
    fin>>A;
    fin>>n;
    for (int i=1;i<=n;i++) {
        fin>>s;

        w[i] = adauga(root, s);
    }

    // construim la fiecare nod back

    Q.push(root);

    while (!Q.empty()) {
        nod = Q.front();
        Q.pop();

        for (int i=0;i<26;i++) {
            if (nod->f[i]) {
                // construim back pentru nod->f[i]
                aux = nod->back;
                while (aux && aux->f[i] == NULL)
                    aux = aux->back;

                if (aux == 0)
                    nod->f[i]->back = root;
                else
                    nod->f[i]->back = aux->f[i];

                nod->f[i]->back->v.push_back(nod->f[i]);

                Q.push(nod->f[i]);
            }
        }

    }

    aux = root; // aux va reprezenta nodul din trie corespunzator caracterului la care sunt in A
    for (int i=0;A[i]!=0;i++) {
        while (aux!=root && aux->f[A[i]-'a'] == NULL)
            aux = aux->back;
        if (aux->f[A[i]-'a'] != NULL)
            aux = aux->f[A[i]-'a'];
        aux->sol++;
    }

    dfs(root);

    for (int i=1;i<=n;i++)
        fout<<w[i]->sol<<"\n";

    return 0;
}