Pagini recente » Cod sursa (job #454290) | Cod sursa (job #2741259) | Cod sursa (job #1248269) | Istoria paginii runda/bisgbyyyyyy/clasament | Cod sursa (job #1812109)
#include <fstream>
#include <vector>
#include <deque>
std::ifstream in ( "ahocorasick.in" );
std::ofstream out( "ahocorasick.out" );
const int DIM = 105;
const int EXP = 10005;
const int LEN = 1000005;
int x;
struct T {
int cntw, cntc, cnto;
std::vector<T*> fte;
T *chl[26], *bke;
T() {
this -> cntw = this -> cntc = this -> cnto = 0; this -> bke = NULL;
for( int i = 0; i < 26; i ++ ) { this -> chl[i] = NULL; } }
} *r = new T;
void insert( T *n, char *str ) {
if( *str == 0 ) {
n -> cntw ++; return; }
else {
if( n -> chl[*str - 'a'] == NULL ) {
n -> chl[*str - 'a'] = new T; n -> cntc ++; }
insert( n -> chl[*str - 'a'], str + 1 ); }
return; }
void build( T *st ) {
std::deque<T*> que; que.push_back( st );
while( que.empty() == false ) {
T *n = que.front(); que.pop_front();
for( int i = 0; i < 26; i ++ ) {
if( n -> chl[i] == NULL ) {
continue; }
T *aux = n -> bke;
while( aux != NULL && aux -> chl[i] == NULL ) {
aux = aux -> bke; }
if( aux == NULL ) {
n -> chl[i] -> bke = r; }
else {
n -> chl[i] -> bke = aux -> chl[i]; }
n -> chl[i] -> bke -> fte.push_back( n -> chl[i] );
que.push_back( n -> chl[i] ); } }
return; }
void psum( T *n ) {
for( auto nxt : n -> fte ) {
psum( nxt ); n -> cnto += nxt -> cnto; }
return; }
int cntocc( T *n, char *str ) {
if( *str == 0 ) {
return n -> cnto; }
if( n -> chl[*str - 'a'] == 0 ) {
return 0; }
return cntocc( n -> chl[*str - 'a'], str + 1 ); }
char wrd[DIM][EXP], str[LEN];
int main( int argc, const char *argv[] ) {
std::ios::sync_with_stdio( false );
int n; in >> str >> n; x = strlen( str );
for( int i = 1; i <= n; i ++ ) {
in >> wrd[i];
insert( r, wrd[i] ); }
build( r ); T *aux = r;
for( int i = 0; str[i] != 0; i ++ ) {
while( aux != r && aux -> chl[str[i] - 'a'] == NULL ) {
aux = aux -> bke; }
if( aux -> chl[str[i] - 'a'] != NULL ) {
aux = aux -> chl[str[i] - 'a']; }
aux -> cnto ++; }
psum( r );
for( int i = 1; i <= n; i ++ ) {
out << cntocc( r, wrd[i] ) << std::endl; }
return 0; }