Cod sursa(job #1218320)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 10 august 2014 14:39:00
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");

struct trie {
    int nr;
    trie *fiu[26], *back;
    vector<trie*> v;
    trie () {
        nr = 0;
        back = NULL;
        for (int i=0; i<26; ++i)
            fiu[i] = NULL;
    }
} *T = new trie;

trie *Rez[105];

queue<trie*> Q;

char A[1000005], s[10005];

int n;

trie *Update (trie *nod, char *s) {
    if (*s == 0)
        return nod;
    if (nod->fiu[*s - 'a'] == NULL)
        nod->fiu[*s - 'a'] = new trie;
    return Update (nod->fiu[*s - 'a'], s+1);
}

void DFS (trie *nod) {
    for (vector<trie*>::iterator it=nod->v.begin(); it!=nod->v.end(); ++it) {
        DFS (*it);
        nod->nr += (*it)->nr;
    }
}

int main () {
    f >> A;
    f >> n;
    for (int i=1; i<=n; ++i) {
        f >> s;
        Rez[i] = Update (T, s);
    }
    Q.push (T);
    while ( !Q.empty() ) {
        trie *nod = Q.front ();
        Q.pop ();
        for (int i=0; i<26; ++i) {
            if (nod->fiu[i] != NULL) {
                trie *aux = nod->back;
                while (aux && !aux->fiu[i])
                    aux = aux->back;
                if (!aux)
                    nod->fiu[i]->back = T;
                else
                    nod->fiu[i]->back = aux->fiu[i];
                nod->fiu[i]->back->v.push_back (nod->fiu[i]);
                Q.push (nod->fiu[i]);
            }
        }
    }
    char *p;
    trie *aux;
    for (p = A, aux = T; *p; ++p) {
        while (aux && !aux->fiu[*p - 'a'])
            aux = aux->back;
        if (!aux)
            aux = T;
        else
            aux = aux->fiu[*p - 'a'];
        ++aux->nr;
    }
    DFS (T);
    for (int i=1; i<=n; ++i)
        g << Rez[i]->nr << "\n";
    return 0;
}