Pagini recente » Cod sursa (job #923449) | Cod sursa (job #1839619) | Cod sursa (job #1343135) | Cod sursa (job #253873) | Cod sursa (job #1089491)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#define NMAX 105
#define QMAX 1000005
#define alpha 97
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[NMAX];
int Number_Words , K , Answer [ NMAX];
char String[NMAX] , Word[NMAX];
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 ( 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 or 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 ( vector < int > ::iterator it = Node->S.begin() ; it != Node->S.end() ; ++it )
Answer [ *it] = 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 )
{
in >> Word[NMAX] ;
strcat ( Word , "\n");
Insert( A , Word , i );
}
AhoCorasick();
for ( i = 1 ; i <= Number_Words ; out << Answer[i++]<<"\n" );
in.close();
out.close();
return 0;
}