Pagini recente » Cod sursa (job #2688390) | Cod sursa (job #589289) | Cod sursa (job #782916) | Cod sursa (job #1984886) | Cod sursa (job #1473132)
/**
* Code by Patrick Sava
* "Spiru Haret" National College of Bucharest
**/
# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"
const char IN [ ] = "ahocorasick.in" ;
const char OUT [ ] = "ahocorasick.out" ;
const int MAX = 1009999 ;
const int WORD = 10099 ;
const int LEN = 199 ;
# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( int a = b ; a >= c ; -- a )
using namespace std ;
ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;
char sir [ MAX ] ;
char cuvant [ MAX ] ;
struct TRIE {
int nr ;
TRIE *fail ;
TRIE *child [ 27 ] ;
TRIE ( )
{
nr = 0 ;
fail = NULL ;
memset ( child , NULL , sizeof ( child ) ) ;
}
};
TRIE *radacina = new TRIE ;
TRIE *capat [ LEN ] , *Q [ WORD * LEN ] ;
inline void baga ( TRIE *nod , char *x , int indice )
{
int c = (*x) - 'a' + 1 ;
if ( c < 1 or c > 26 )
{
capat [ indice ] = nod ;
return ;
}
if ( nod -> child [ c ] == NULL )
nod -> child [ c ] = new TRIE ;
baga ( nod -> child [ c ] , x + 1 , indice ) ;
}
int main ( void )
{
cin >> ( sir + 1 ) ;
int n ;
cin >> n ;
FORN ( i , 1 , n )
{
cin >> cuvant ;
baga ( radacina , cuvant , i ) ;
}
int p = 1 ;
int u = 1 ;
Q [ 1 ] = radacina ;
radacina -> fail = radacina ;
while ( p <= u )
{
TRIE *nod = Q [ p ] ;
FORN ( c , 1 , 26 )
{
if ( nod -> child [ c ] == NULL ) continue ;
TRIE *suf = nod -> fail ;
while ( suf -> child [ c ] == NULL and suf != radacina )
suf = suf -> fail ;
if ( suf -> child [ c ] != NULL and suf -> child [ c ] != nod -> child [ c ] )
nod -> child [ c ] -> fail = suf -> child [ c ] ;
else nod -> child [ c ] -> fail = radacina ;
++ u ;
Q [ u ] = nod -> child [ c ] ;
}
++ p ;
}
TRIE *nod = radacina ;
int l = strlen ( sir + 1 ) ;
FORN ( i , 1 , l )
{
int c = sir [ i ] - 'a' + 1 ;
while ( nod != radacina and nod -> child [ c ] == NULL )
nod = nod -> fail ;
if ( nod -> child [ c ] != NULL )
nod = nod -> child [ c ] ;
nod -> nr ++ ;
}
FORNBACK ( i , u , 1 )
{
Q [ i ] -> fail -> nr += Q [ i ] -> nr ;
}
FORN ( i , 1 , n )
cout << capat [ i ] -> nr << '\n' ;
return 0;
}