Pagini recente » Cod sursa (job #613430) | Cod sursa (job #1076115)
#include<fstream>
#include<vector>
using namespace std ;
#define Nmax 110
#define Lmax 10010
#define Amax 100010
#define L_alfabet 26
ifstream f ("ahocorasick.in");
ofstream g("ahocorasick.out");
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 () {
int i, N ;
f>>A>>N;
for( i = 1 ; i <= N ; i++ )
f>>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++ )
g<<query(T,D[i])<<'\n';
f.close();
g.close();
return 0 ;
}