Cod sursa(job #742363)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 29 aprilie 2012 20:44:53
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 kb
#include<fstream>
#include<vector>
using namespace std ;

#define Nmax 110
#define Lmax 10010
#define Amax 1000010
#define L_alfabet 26

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 () 
{
	ifstream in ("ahocorasick.in");
	ofstream out("ahocorasick.out");
	
	int i, N ;
	
	in>>A>>N;
	
	for( i = 1 ; i <= N ; i++ )
		in>>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++ )
		out<<query(T,D[i])<<'\n';
	
	in.close();
	out.close();
	
	return 0 ; 
}