Pagini recente » Cod sursa (job #2125420) | Cod sursa (job #1660454) | Cod sursa (job #2137418) | Cod sursa (job #2806542) | Cod sursa (job #1089681)
#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;
}