Cod sursa(job #1076117)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 9 ianuarie 2014 21:51:19
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.61 kb
#include<fstream>
#include<vector>
using namespace std ;
 
#define Nmax 110
#define Lmax 10010
#define Amax 1000010
#define L_alfabet 26
 
ifstream f ("ahocorasick.in");
ofstream g("ahocorasick.out");
char A[Amax], D[Nmax][Lmax] ; 
int niveluri ;
 
struct Trie {
    int inf ;
    char ch ;
     
    Trie* links[L_alfabet] ; 
    Trie* back, *p ;
     
    Trie( Trie* P, char c ) {
        inf = 0 ;
        ch = c;
        back = NULL ;
        p = P ;
        for( int i = 0 ; i < L_alfabet ; i++ )
            links[i] = NULL ; 
    }
} *T ; 
 
vector< Trie* > Nivel[Lmax] ;
 
void add_cuv ( Trie *&nod, char *c, int lvl ) {
    if( *c == '\0' ) return ;
    int link = *c - 'a' ; 
    if( nod->links[link] == NULL ){
        nod->links[link] = new Trie(nod,*c) ;
        Nivel[lvl+1].push_back(nod->links[link]);
        if( lvl+1 > niveluri ) niveluri = lvl+1 ;
    }
    add_cuv( nod->links[link], c+1, lvl+1 ) ;
}
 
void set_back_links () {
    Trie *link ;
     
    for( int i = 1 ; i <= niveluri ; i++ ){
        for( vector<Trie*> :: iterator it = Nivel[i].begin() ; it != Nivel[i].end() ; it++ ){
            link = (*it)->p->back ; 
            while( link ) {
                if( link->links[ (*it)->ch - 'a' ] ) {
                    link = link->links[ (*it)->ch - 'a' ] ; 
                    break ; 
                }
                link = link->back ;
            }
            if(link)
                (*it)->back = link ; 
            else
                (*it)->back = T ;
        }
    }
}
 
void search ( Trie *nod, char *c ){   
    if ( *c == '\0' ) return ; 
    if( nod == NULL ){
        search( T, c+1 ) ;
        return ; 
    }
    int link = (*c) - 'a' ;
     
    if( nod->links[link] ) {
        nod->links[link]->inf++;
        search(nod->links[link],c+1);
    }
    else
        search(nod->back,c);
}
 
 
void update () {
    for( int i = niveluri ; i > 0 ; i-- ) 
        for( vector<Trie*> :: iterator it = Nivel[i].begin() ; it != Nivel[i].end() ; it++ ) 
            (*it)->back->inf += (*it)->inf ; 
}
 
int query ( Trie* nod, char *c ){
    if( *c == '\0' )
        return nod->inf ;
 
    return query( nod->links[(*c)-'a'],c+1);
}
 
int main () {
    
    int i, N ;
     
    f>>A>>N;
     
    for( i = 1 ; i <= N ; i++ )
        f>>D[i];
    T=new Trie(T,'\0');
    T->p = T ; 
    for(i=1;i<=N;i++)
        add_cuv(T,D[i],0);
    set_back_links() ;
    search(T,A);
    update() ;
 
    for( i = 1 ; i <= N ; i++ )
        g<<query(T,D[i])<<'\n';
    f.close();
    g.close();
     
    return 0 ; 
}