Cod sursa(job #1089681)

Utilizator superman_01Avramescu Cristian superman_01 Data 21 ianuarie 2014 21:06:19
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define NMAX 105
#define QMAX 1000010
#define alpha 'a'
#define LMAX 1000005
#define WMAX 10005

using namespace std;

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

struct Trie 
{
	vector < int >  S;
	int NS ;
	Trie *Son[26] , *Fail ;
	Trie ()
	{
		NS = 0 ;
		Fail = NULL;
		memset ( Son , 0 ,sizeof (Son) );
	}
}; 
Trie  *A , *Q[QMAX];
int Number_Words , K , Answer [ NMAX]; 
char String[LMAX] , Word[WMAX];

void Insert ( Trie *Node , char *Letter , int i )
{
	if ( *Letter == '\n' )
	{
		Node->S.push_back( i );
		return ;
	}
	if ( Node->Son[*Letter - alpha ] == NULL )
		Node->Son[*Letter - alpha] = new Trie;
	Insert ( Node->Son[*Letter - alpha] , Letter + 1 , i );
}

void BFS ( void )
{
	int i  , j ;
	A->Fail=A; 
	K = 1 ; 
	Q[1] = A ;
	for ( i = 1 ; i <= K ; ++i )
	{
		 Trie *Node=Q[i];
        for (int j=0; j<26; ++j)
        {
            Trie *CFail;
            if (Node->Son[j]==NULL)
            {
                continue;
            }
            for (CFail=Node->Fail; CFail!=A and CFail->Son[j]==NULL; CFail=CFail->Fail);
            if (CFail->Son[j]!=NULL and CFail->Son[j]!=Node->Son[j])
                CFail=CFail->Son[j];
			
            Node->Son[j]->Fail=CFail;
            Q[++K]=Node->Son[j];
        }
	}
		A->Fail = NULL;
}

void AntiBFS ( void )
{
	int i , j ;
	for ( i = K ; i > 0 ; --i )
	{
		Trie *Node = Q[i];
		if ( Node->Fail != NULL )
		Node->Fail->NS+= Node->NS;
		for ( j = 0 ; j < Node->S.size() ; ++j )
			Answer[Node->S[j] ] = Node->NS;
	}
}
void AhoCorasick ( void )
{
	BFS();
	int len = strlen ( String );
	Trie *Node = A;
	int  i , j ;
	for ( i = 0 ; i < len ; ++i )
	{
		int letter = String[i] - alpha;
		for ( ;Node != A and Node->Son[letter] == NULL ; Node = Node->Fail );
			if ( Node->Son[letter] != NULL )
				Node = Node->Son[letter];
		++Node->NS;
	}
	AntiBFS();
}

int main ( void )
{
	int i ;
	A = new Trie ;
	in >> String >> Number_Words;
	for ( i = 1 ; i <= Number_Words ; ++i )
	{
		memset ( Word , 0 , sizeof(Word) );
		in >> Word ; 
		strcat ( Word , "\n");
		Insert( A , Word  , i );
		
	}
	AhoCorasick();
	for ( i = 1 ;  i <= Number_Words ; out << Answer[i++]<<"\n" );
	in.close();
	out.close();
	return 0;
}