Cod sursa(job #1473132)

Utilizator xtreme77Patrick Sava xtreme77 Data 18 august 2015 17:08:47
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.81 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 "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "ahocorasick.in" ;
const char OUT [ ] = "ahocorasick.out" ;
const int MAX = 1009999 ;
const int WORD = 10099 ;
const int LEN = 199 ;

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

using namespace std ;

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

char sir [ MAX ] ;
char cuvant [ MAX ] ;

struct TRIE {
    int nr ;
    TRIE *fail ;
    TRIE *child [ 27 ] ;

    TRIE ( )
    {
        nr = 0 ;
        fail = NULL ;
        memset ( child , NULL , sizeof ( child ) ) ;
    }
};

TRIE *radacina = new TRIE ;

TRIE *capat [ LEN ] , *Q [ WORD * LEN ] ;

inline void baga ( TRIE *nod , char *x , int indice )
{
    int c = (*x) - 'a' + 1 ;
    if ( c < 1 or c > 26 )
    {
        capat [ indice ] = nod ;
        return ;
    }
    if ( nod -> child [ c ] == NULL )
        nod -> child [ c ] = new TRIE ;
    baga ( nod -> child [ c ] , x + 1 , indice ) ;
}

int main ( void )
{
    cin >> ( sir + 1 ) ;
    int n ;
    cin >> n ;
    FORN ( i , 1 , n )
    {
        cin >> cuvant ;
        baga ( radacina , cuvant , i ) ;
    }
    int p = 1 ;
    int u = 1 ;
    Q [ 1 ] = radacina ;
    radacina -> fail = radacina ;

    while ( p <= u )
    {
        TRIE *nod = Q [ p ] ;

        FORN ( c , 1 , 26 )
        {
            if ( nod -> child [ c ] == NULL ) continue ;

            TRIE *suf = nod -> fail ;

            while ( suf -> child [ c ] == NULL and suf != radacina )
                suf = suf -> fail ;

            if ( suf -> child [ c ] != NULL and suf -> child [ c ] != nod -> child [ c ] )
                nod -> child [ c ] -> fail = suf -> child [ c ] ;
            else nod -> child [ c ] -> fail = radacina ;

            ++ u ;
            Q [ u ] = nod -> child [ c ] ;
        }

        ++ p ;
    }

    TRIE *nod = radacina ;

    int l = strlen ( sir + 1 ) ;

    FORN ( i , 1 , l )
    {
        int c = sir [ i ] - 'a' + 1 ;

        while ( nod != radacina and nod -> child [ c ] == NULL )
            nod = nod -> fail ;
        if ( nod -> child [ c ] != NULL )
            nod = nod -> child [ c ] ;

        nod -> nr ++ ;
    }

    FORNBACK ( i , u , 1 )
    {
        Q [ i ] -> fail -> nr += Q [ i ] -> nr ;
    }
    FORN ( i , 1 , n )
        cout << capat [ i ] -> nr << '\n' ;

    return 0;
}