Cod sursa(job #1305570)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 29 decembrie 2014 21:44:52
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define dt 1000005
#define dc 10005

char text[dt],cuv[dc];
int n ,inc , fin     ;
int sum[dc];

struct trie{
    trie *fiu[26],*fail;
    int n0;
    vector<int> v;
    trie(){
        memset(fiu,0,sizeof(fiu));
        fail = NULL;
        n0 = 0;
    }
};

trie *t = new trie , *q[dc*dc],*p;

void insert( trie *nod , char *c , int i ){
    if( *c == '\0' ){
        nod->v.push_back(i);
        return ;
    }
    int urm = *c - 'a';
    if(    nod->fiu[urm] == 0 ) nod->fiu[urm] = new trie;
    insert(nod->fiu[urm] , c+1, i );

}

void bfs(trie *nod){
    trie *fail,*tmp;
    nod->fail = nod;
    for( q[ inc = fin = 1 ] = nod;inc <= fin ;++inc ){
        tmp = q[inc];
        for(int i=0;i<26;++i)
            if( tmp->fiu[i] != NULL ){
                for( fail = tmp->fail; fail != nod && fail->fiu[i] == NULL; fail = fail->fail );
                if( fail->fiu[i] != NULL && fail->fiu[i] != tmp->fiu[i] ) fail = fail->fiu[i];
                tmp->fiu[i]->fail = fail;
                q[++fin] = tmp->fiu[i];
            }
    }
    nod->fail = NULL;
}

void antibfs(){
    trie *tmp;
    for(int i=fin; i ; --i){
        tmp = q[i];
        if( tmp->fail != NULL ) tmp->fail->n0 += tmp->n0;
        for(int j=0; j < tmp->v.size(); ++j) sum[ tmp->v[j] ] = tmp->n0;
    }


}

int main()
{
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);

    scanf("%s",text);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%s",cuv);
        insert(t,cuv,i);
    }
    bfs(t);

    p = t;

    int len = strlen(text);
    for(int i = 0; i < len; ++i){
        int urm = text[i] - 'a';
        for( ; p->fiu[urm]==NULL && p!=t ; p = p->fail);
        if( p->fiu[urm] != NULL  ) p = p->fiu[urm];
        ++p->n0;
    }
    antibfs();
    for(int i=1; i<=n; ++i) printf("%d\n",sum[i]);

    return 0;
}