Cod sursa(job #1673935)

Utilizator margikiMargeloiu Andrei margiki Data 4 aprilie 2016 11:24:59
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
# include <bits/stdc++.h>
# define NR 1000005
# define L 10005
# define sigma 26
# define CH (*s - 'a')
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
struct trie {
    int nr; //numarul de potriviri
    trie *fiu[sigma], *fail;
    vector <trie*> adj;
    trie() {
        nr=0; fail=NULL;
        memset (fiu, 0, sizeof(fiu));
        adj.clear();
    }
}*poz[105];
trie *T=new trie;
int i,j,n,m;
char s[NR], var[L];
trie *ins (trie *nod, char *s) {
    if (*s=='\0') return nod;

    if (nod->fiu[CH]==NULL)
        nod->fiu[CH] = new trie;
    return ins (nod->fiu[CH], s+1);
}
void BFS () {
    queue <trie*> q;
    q.push(T);
    while (! q.empty()) {
        trie *nod=q.front(); q.pop();
        for (int i=0; i<26; ++i) {
            if (nod->fiu[i]==NULL) continue;

            trie *aux=nod->fail;
            while (aux!=NULL && aux->fiu[i]==NULL)
                aux=aux->fail;

            if (aux==NULL) aux=T;
                      else aux=aux->fiu[i];
            nod->fiu[i]->fail = aux;
            aux->adj.push_back(nod->fiu[i]);

            q.push(nod->fiu[i]);
        }
    }
}
void DFS (trie *nod) {
    for (vector<trie*>::iterator adj = nod->adj.begin(); adj != nod->adj.end(); ++adj) {
        DFS(*adj);
        nod->nr += (*adj)->nr;
    }
}
int main ()
{
    f.getline (s+1, NR); n=strlen(s+1);
    f>>m; f.get();
    for (i=1; i<=m; ++i) {
        f.getline (var+1, L);
        poz[i]=ins (T, var+1);
    }
    BFS ();

    trie *curr=T;
    for (int i=1; i<=n; ++i) {
        while (curr && curr->fiu[s[i]-'a']==NULL)
            curr=curr->fail;
        if (curr==NULL) curr=T;
                   else curr=curr->fiu[s[i]-'a'];
        curr->nr ++;
    }
    DFS (T);
    for (i=1; i<=m; ++i)
        g<<poz[i]->nr<<"\n";

    return 0;
}