Cod sursa(job #1220788)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 18 august 2014 16:06:05
Problema Aho-Corasick Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");

char a[1000010],s[10010];
int n,i;

struct trie {
    int nr;
    trie *f[26],*back;
    vector <trie*> v;
    trie () {
        nr=0;
        back=0;
        for (i=0;i<26;i++)
            f[i]=0;
    }
} *r= new trie, *nod, *aux, *w[110];

queue <trie*> q;

trie *update (trie *nod, char *p) {
    if (*p==0)
        return nod;
    if (nod->f[*p-'a']==0)
        nod->f[*p-'a']=new trie;
    return update(nod->f[*p-'a'], p+1);
}

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

int main () {

    fin>>a;
    fin>>n;
    for (int i=1;i<=n;i++) {
        fin>>s;
        w[i]=update (r,s);
    }
    q.push(r);
    while (!q.empty()){
        nod = q.front();
        q.pop();
        for (i=0;i<26;i++) {
            if (nod->f[i]!=0) {
                q.push (nod->f[i]);
                aux=nod->back;
                while (aux && !aux->f[i])
                    aux=aux->back;
                if (!aux)
                    nod->f[i]->back=r;
                else
                    nod->f[i]->back=aux->f[i];
                nod->f[i]->back->v.push_back(nod->f[i]);
            }
        }
    }
    for (i=0 , aux=r;i<strlen(a);i++){
        while (aux && !aux->f[a[i]-'a'])
            aux=aux->back;
        if (!aux)
            aux=r;
        else
            aux=aux->f[a[i]-'a'];
        aux->nr++;
    }
    dfs(r);

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

    return 0;
}