Cod sursa(job #1171821)

Utilizator teoionescuIonescu Teodor teoionescu Data 16 aprilie 2014 13:44:15
Problema Aho-Corasick Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
const int Nmax = 1000100;
const int Lmax = 10100;
char A[Nmax],B[Lmax];
int Many[101];
int N;
struct trie{
    char c;
    vector<int> is;
    trie* to[27];
    trie *tata,*fail,*megafail;
    trie(){}
    trie(int _c,trie* _t){c=_c,tata=_t;}
    int isnext(char C){
        int co=int(C)-'a';
        return to[co]!=NULL;
    }
    trie* next(char C){
        int co=int(C)-'a';
        return to[co];
    }
    trie* nextad(char C){
        int co=int(C)-'a';
        trie* t=new trie(C,this);
        to[co]=t;
        return t;
    }
};
trie* R;
void push(int ind,char *s){
    trie* t=R;
    for(char c=*s;*s;s++,c=*s){
        if(t->isnext(c)) t=t->next(c);
        else t=t->nextad(c);
    }
    t->is.push_back(ind);
}
queue<trie*> q;
trie* findfail(trie* t){
    int C=t->c;
    t=(t->tata)->fail;
    while(t!=R && !t->isnext(C)) t=t->fail;
    if(t->isnext(C)) return t->next(C);
    return t;
}
trie* findmegafail(trie* t){
    t=t->fail;
    while(t!=R){
        if(t->is.size()) return t;
        t=t->fail;
    }
    return t;
}
void increment(trie *t){
    while(t!=R){
        if(t->is.size()) for(vector<int>::iterator it=t->is.begin();it!=t->is.end();++it) Many[*it]++;
        t=t->megafail;
    }
}
void process(char *s){
    trie* t=R;
    for(char c=*s;*s;s++,c=*s){
        while(t!=R && !t->isnext(c)) t=t->fail;
        if(t->isnext(c)) t=t->next(c);
        increment(t);
    }
}
int main(){
    R=new trie(0,0);
    in.getline(A,Nmax);
    in>>N;in.get();
    for(int i=1;i<=N;i++){
        in.getline(B,Lmax);
        push(i,B);
    }
    for(char C='a';C<='z';C++){
        int co=int(C)-'a';
        if(R->to[co]!=NULL){
            R->to[co]->fail=R;
            R->to[co]->megafail=R;
            q.push(R->to[co]);
        }
    }
    while(!q.empty()){
        trie* t=q.front(); q.pop();
        if(!t->fail){
            t->fail=findfail(t);
            t->megafail=findmegafail(t);
        }
        for(char C='a';C<='z';C++){
            int co=int(C)-'a';
            if(t->to[co]!=NULL) q.push(t->to[co]);
        }
    }
    process(A);
    for(int i=1;i<=N;i++) out<<Many[i]<<'\n';
    return 0;
}