Pagini recente » Cod sursa (job #2367640) | Cod sursa (job #675290) | Cod sursa (job #298111) | Cod sursa (job #589208) | Cod sursa (job #1688598)
/**
* 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 "set"
# 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" ;
using namespace std ;
# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )
ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;
struct Trie {
Trie *next [ 27 ] ;
Trie *suff ;
int cate ;
Trie ( )
{
memset ( next , 0 , sizeof ( next ) ) ;
suff = NULL ;
cate = 0 ;
}
};
Trie *Root = new Trie ;
char sir [ 1000999 ] ;
char cuvant [ 10099 ] ;
vector < pair < Trie *, int > > noduri ;
int solution [ 114 ] ;
inline void baga ( Trie *nod , char *p , int len , int h , int i )
{
if ( h == len + 1 ) {
noduri.pb ( mp ( nod , i ) ) ;
return ;
}
if ( nod -> next [ *p - 'a' ] == NULL ) {
nod -> next [ *p - 'a' ] = new Trie ;
}
baga ( nod -> next [ *p - 'a' ] , p + 1 , len , h + 1 , i ) ;
}
queue < Trie * > Q ;
stack < Trie * > invers ;
int main ( void )
{
cin >> ( sir + 1 ) ;
int cuv ;
cin >> cuv ;
FORN ( i , 1 , cuv ) {
cin >> ( cuvant + 1 ) ;
baga ( Root , cuvant + 1 , strlen ( cuvant + 1 ) , 1 , i ) ;
}
Q.push( Root ) ;
while ( !Q.empty() )
{
Trie *nod = Q.front() ;
invers.push ( nod ) ;
Q.pop ( ) ;
FORN ( i , 0 , 25 ) {
if ( nod -> next [ i ] != NULL ) {
Q.push ( nod -> next [ i ] ) ;
Trie *aux = nod -> next [ i ] ;
Trie *suftata = nod -> suff ;
while ( suftata != Root and suftata != NULL and suftata -> next [ i ] == NULL ) {
suftata = suftata -> suff ;
}
if ( suftata == NULL or suftata == Root ) {
suftata = Root ;
if ( Root -> next [ i ] == NULL or Root -> next [ i ] == aux ){
aux -> suff = Root ;
}
else {
aux -> suff = Root -> next [ i ] ;
}
}
else {
aux -> suff = suftata -> next [ i ] ;
}
}
}
}
Trie *cur = Root ;
int l = strlen ( sir + 1 ) ;
FORN ( i , 1 , l ) {
if ( cur == NULL ) {
cur = Root ;
}
while ( cur != Root and cur != NULL and cur -> next [ sir [ i ] - 'a' ] == NULL ) {
cur = cur -> suff ;
}
if ( cur != NULL ){
if ( cur -> next [ sir [ i ] - 'a' ] != NULL ) {
cur = cur -> next [ sir [ i ] - 'a' ] ;
cur -> cate ++ ;
}
}
}
Root -> suff = Root ;
while ( invers.empty() == 0 )
{
Trie *nod = invers.top() ;
invers.pop() ;
nod -> suff -> cate += nod -> cate ;
}
for ( auto x : noduri ) {
solution [ x.second ] = x.first -> cate ;
}
FORN ( i , 1 , cuv ) {
cout << solution [ i ] << '\n' ;
}
return 0;
}