Cod sursa(job #2067108)

Utilizator tqmiSzasz Tamas tqmi Data 15 noiembrie 2017 20:43:00
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

struct ac{
    vector <int> ind;
    ac* son[26];
    ac* fail;
    int nr;
    ac(){
        memset(son,0,sizeof(son));
        fail = 0;
        nr = 0;
    }
};

ac *t = new ac();
int N,K;
char S[1000005];
char c[10005];
ac *Q[100000005];
int sol[1000005];

void add(ac* nod,char* s,int index){
    if(!isalpha(*s)){
        nod->ind.push_back(index);
        return;
    }
    if(nod->son[*s-'a']==0){
        nod->son[*s-'a'] = new ac();
    }
    add(nod->son[*s-'a'],s+1,index);
}

void BFS(){
    t->fail = t;
    Q[++K] = t;
    for(int i=1;i<=K;i++){
        ac* nod = Q[i];
        for(int j=0;j<26;j++){
            ac* son = nod->son[j];
            if(son==0) continue;
            ac* cf = nod->fail;
            while(cf->son[j]==0 && cf!=t) cf = cf->fail;
            if(cf == t && t->son[j]==0)
                son->fail = t;
            else
                son->fail = cf->son[j];
            if(son->fail == son)
                son->fail = t;
            Q[++K] = son;
        }
    }
    t->fail=0;
}

void ABFS(){
    for(int i=K;i>0;i--){
        ac* nod = Q[i];
        if(nod->fail)
            nod->fail->nr+=nod->nr;
        for(int j=0;j<nod->ind.size();j++)
            sol[nod->ind[j]] = nod->nr;
    }
}

void solve(){
    ac* nod = t;
    for(int i=0;S[i];i++){
        int c = S[i]-'a';
        while(nod->son[c]==0 && nod!=t) nod = nod->fail;
        if(nod->son[c]){
            nod=nod->son[c];
            nod->nr++;
        }
    }
}

int main()
{
    fin>>S;
    fin>>N;
    for(int i=1;i<=N;i++)
    {
        fin>>c;
        add(t,c,i);
    }
    BFS();
    solve();
    ABFS();
    for(int i=1;i<=N;i++){
        fout<<sol[i]<<"\n";
    }
    return 0;
}