Cod sursa(job #1719818)

Utilizator MaarcellKurt Godel Maarcell Data 20 iunie 2016 13:59:39
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cstring>
#include <string>
using namespace std;

struct Trie{
    Trie *next[26],*fail;
    vector<int> ind;
    int cnt;
    Trie(){
        memset(next,0,sizeof(next));
        fail=NULL,cnt=0;
    }
};

Trie *root=new Trie(),*q[500000];
int N,M,L,ans[110],K;
string A,B;

void ins(Trie *&nod, int k, int ind){
    if (nod==NULL) nod=new Trie();
    if (k>=L){
        nod->ind.push_back(ind);
        return;
    }

    ins(nod->next[B[k]-'a'],k+1,ind);
}

void calc_fail(){
    Trie *aux,*nod; root->fail=root;
    K=1,q[1]=root;
    int i,j;

    for (i=1; i<=K; i++){
        nod=q[i];
        for (j=0; j<26; j++)
            if (nod->next[j]!=NULL){
                aux=nod->fail;
                while (aux->next[j]==NULL && aux!=root) aux=aux->fail;
                nod->next[j]->fail=aux->next[j];
                if (aux->next[j]==NULL || aux==nod) nod->next[j]->fail=root;
                q[++K]=nod->next[j];
            }
    }
}

void rbfs(){
    int i,j; Trie *nod;
    for (i=K; i>0; i--){
        nod=q[i];
        nod->fail->cnt+=nod->cnt;
        for (j=0; j<nod->ind.size(); j++)
            ans[nod->ind[j]]=nod->cnt;
    }
}

int main(){
    ifstream fin("ahocorasick.in");
    ofstream fout("ahocorasick.out");
    fin >> A;
    fin >> M;

    int i;
    N=A.length();
    for (i=1; i<=M; i++){
        fin >> B;
        L=B.length();
        ins(root,0,i);
    }
    calc_fail();

    Trie *cr=root;
    for (i=0; i<N; i++){
        while (cr!=root && cr->next[A[i]-'a']==NULL)
            cr=cr->fail;
        if (cr->next[A[i]-'a']) cr=cr->next[A[i]-'a'];
        cr->cnt++;
    }

    rbfs();
    for (i=1; i<=M; i++) fout << ans[i] << "\n";

    return 0;
}