Cod sursa(job #1688598)

Utilizator xtreme77Patrick Sava xtreme77 Data 13 aprilie 2016 16:57:45
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.53 kb
/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "ahocorasick.in" ;
const char OUT [ ] = "ahocorasick.out" ;

using namespace std ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )

ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;

struct Trie {
    Trie *next [ 27 ] ;
    Trie *suff ;
    int cate ;
    Trie ( )
    {
        memset ( next , 0 , sizeof ( next ) ) ;
        suff = NULL ;
        cate = 0 ;
    }
};

Trie *Root = new Trie ;

char sir [ 1000999 ] ;
char cuvant [ 10099 ] ;

vector < pair < Trie *, int > > noduri ;

int solution [ 114 ] ;

inline void baga ( Trie *nod , char *p , int len , int h , int i )
{
    if ( h == len + 1 ) {
        noduri.pb ( mp ( nod , i ) ) ;
        return ;
    }
    if ( nod -> next [ *p - 'a' ] == NULL ) {
        nod -> next [ *p - 'a' ] = new Trie ;
    }
    baga ( nod -> next [ *p - 'a' ] , p + 1 , len , h + 1 , i ) ;
}

queue < Trie * > Q ;
stack < Trie * > invers ;

int main ( void )
{
    cin >> ( sir + 1 ) ;
    int cuv ;
    cin >> cuv ;
    FORN ( i , 1 , cuv ) {
        cin >> ( cuvant + 1 ) ;
        baga ( Root , cuvant + 1 , strlen ( cuvant + 1 ) , 1 , i ) ;
    }
    Q.push( Root ) ;
    while ( !Q.empty() )
    {
        Trie *nod = Q.front() ;
        invers.push ( nod ) ;
        Q.pop ( ) ;
        FORN ( i , 0 , 25 ) {
            if ( nod -> next [ i ] != NULL ) {
                Q.push ( nod -> next [ i ] ) ;
                Trie *aux = nod -> next [ i ] ;
                Trie *suftata = nod -> suff ;
                while ( suftata != Root and suftata != NULL and suftata -> next [ i ] == NULL ) {
                    suftata = suftata -> suff ;
                }
                if ( suftata == NULL or suftata == Root ) {
                    suftata = Root ;
                    if ( Root -> next [ i ] == NULL or Root -> next [ i ] == aux ){
                        aux -> suff = Root ;
                    }
                    else {
                        aux -> suff = Root -> next [ i ] ;
                    }
                }
                else {
                    aux -> suff = suftata -> next [ i ] ;
                }
            }
        }
    }
    Trie *cur = Root ;
    int l = strlen ( sir + 1 ) ;
    FORN ( i , 1 , l ) {
        if ( cur == NULL ) {
            cur = Root ;
        }
        while ( cur != Root and cur != NULL and cur -> next [ sir [ i ] - 'a' ] == NULL ) {
            cur = cur -> suff ;
        }
        if ( cur != NULL ){
            if ( cur -> next [ sir [ i ] - 'a' ] != NULL ) {
                cur = cur -> next [ sir [ i ] - 'a' ] ;
                cur -> cate ++ ;
            }
        }
    }
    Root -> suff = Root ;
    while ( invers.empty() == 0 )
    {
        Trie *nod = invers.top() ;
        invers.pop() ;
        nod -> suff -> cate += nod -> cate ;
    }
    for ( auto x : noduri ) {
        solution [ x.second ] = x.first -> cate ;
    }
    FORN ( i , 1 , cuv ) {
        cout << solution [ i ] << '\n' ;
    }
    return 0;
}