Pagini recente » Cod sursa (job #1498462) | Cod sursa (job #140208) | Cod sursa (job #882951) | Cod sursa (job #584509) | Cod sursa (job #935195)
Cod sursa(job #935195)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define Smax 1000005
#define Lmax 10005
#define Nmax 105
#define Sigma 26
struct TRIE{
TRIE *fiu[Sigma], *fail;
int potriviri;
vector <int> nd;
TRIE(){
potriviri = 0;
fail = NULL;
memset(fiu, 0, sizeof(fiu));
}
};
TRIE *T, *Q[ Nmax * Lmax ], *P;
char S[Smax], L[Lmax];
int REZ[Nmax];
int inc, sfc , N;
void adauga ( TRIE *T, char *p, int i ){
if ( !isalpha( *p ) ){
T -> nd.push_back(i);
return;
}
int next = *p - 'a';
if ( T -> fiu[next] == 0 )
T -> fiu[next] = new TRIE;
adauga ( T -> fiu[next], p + 1, i );
}
void BFS( TRIE *T ){
TRIE *tmp;
T -> fail = T;
for ( Q[ inc = sfc = 1 ] = T; inc <= sfc; inc++ ){
TRIE *cr = Q[inc];
for ( int i = 0; i < Sigma; i++ )
if ( cr -> fiu[i] != NULL ){
for ( tmp = cr -> fail; tmp != T && tmp -> fiu[i] == NULL; tmp = tmp -> fail );
if( tmp -> fiu[i] != NULL && tmp -> fiu[i] != cr -> fiu[i] )
tmp = tmp -> fiu[i];
cr -> fiu[i] -> fail = tmp;
Q[ ++sfc ] = cr -> fiu[i];
}
}
T -> fail = NULL;
}
void RevBFS( TRIE *T ){
for ( int i = sfc; i; i-- ){
TRIE *cr = Q[i];
if ( cr -> fail != NULL )
cr -> fail -> potriviri += cr -> potriviri;
for ( unsigned int j = 0; j < cr -> nd.size(); j++ )
REZ[ cr -> nd[j] ] = cr -> potriviri;
}
}
int main(){
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
scanf("%s", S);
scanf("%d", &N);
T = new TRIE;
for ( int i = 1; i <= N; ++i ){
scanf("%s", L);
adauga( T, L, i );
}
BFS( T );
P = T;
int lg = strlen( S );
for ( int i = 0; i < lg; ++i ){
int next = S[i] - 'a';
for ( ; P -> fiu[next] == NULL && P != T; P = P -> fail );
if ( P -> fiu[next] != NULL )
P = P -> fiu[next];
++P -> potriviri;
}
RevBFS( T );
for ( int i = 1; i <= N; ++i )
printf("%d\n", REZ[i]);
return 0;
}