Cod sursa(job #1464757)

Utilizator petru.cehanCehan Petru petru.cehan Data 24 iulie 2015 15:20:28
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
#include <cstring>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

ifstream fin ( "ahocorasick.in" ) ;
ofstream fout ( "ahocorasick.out" ) ;

struct Trie // Arborele Digital
{
    int val ;
    Trie *fiu[26] , *fail ;
    vector < Trie* > V ;

    Trie()
    {
        val = 0 ;
        memset ( fiu , 0 , sizeof ( fiu ) ) ;
        fail = 0 ;
    }
};

Trie * R = new Trie() ;

char A[1000002] , B[10002] ;
Trie * words [102] ;
queue < Trie* > Q ;
int N ;

void Add ( Trie * current , char * word , int ind )
{
    if ( *word == 0 )
    {
        words [ind] = current ;
        return;
    }

    if ( current -> fiu [ *word - 'a' ] == 0 ) // exista litera pe "drumul cuvantului " ??
        current -> fiu [ *word - 'a' ] = new Trie() ;

    Add ( current -> fiu [ *word - 'a' ] , word + 1, ind ) ;
}

void DFS ( Trie * T )
{
    for ( vector < Trie * > :: iterator it = T->V.begin () ; it != T->V.end () ; ++ it )
    {
        DFS ( *it ) ;
        T->val += (*it)->val ;
    }
}

int main()
{
    fin >> A >> N;
    for ( int i = 1 ; i <= N ; ++ i )
    {
        fin >> B ;
        Add ( R , B , i ) ;
    }

    Q.push (R) ; // pun tri-eul in coada
    while ( !Q.empty() )
    {
        Trie * T = Q.front() ;
        Q.pop() ;

        for ( int i = 0 ; i < 26 ; ++ i )
            if ( T -> fiu[i] != 0 )
            {
                Trie * now = T->fail ;
                while ( now != 0 && now->fiu[i] == 0 )
                    now = now->fail ;

                if ( now == 0 )
                {
                    T->fiu[i]->fail = R ;
                    R->V.push_back ( T->fiu[i] ) ;
                }
                else
                {
                    T->fiu[i]->fail = now->fiu[i] ;
                    now->fiu[i]->V.push_back ( T->fiu[i] ) ;
                }

                Q.push ( T->fiu[i] ) ;
            }
    }

    Trie * T = R ;
    for ( int i = 0 ; A[i] != 0 ; ++ i )
    {
        while ( T != 0 && T->fiu [A[i] - 'a'] == 0 )
            T = T->fail ;

        if ( T == 0 ) T = R ;
        else        T = T->fiu [A[i] - 'a'] ;

        ++ T->val ;
    }

    DFS(R) ;

    for ( int i = 1 ; i <= N ; ++ i )
        fout << words [i]->val << '\n' ;

    fin.close() ;
    fout.close() ;

    return 0 ;
}