Pagini recente » Cod sursa (job #35451) | Cod sursa (job #1665100) | Cod sursa (job #713427) | Cod sursa (job #2353377) | Cod sursa (job #1840332)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <queue>
#define LMAX 1000010
#define LEN 100010
#define LENDIC 26
#define NRCUV 110
using namespace std;
struct tries{
vector <tries *> adj;
int nrcuv;
tries *alf[LENDIC] , *fail ;
tries(){
nrcuv = 0;
adj.clear();
fail = NULL;
for ( int i =0 ; i < LENDIC ; i++ ){
alf[i] =NULL ;
}
}
};
struct tries *tr = new tries , *cur , *sol[NRCUV] ;
int k;
char s [LEN] , sircmp [LMAX] ;
tries* ins ( int i , tries *a ){
if ( s[i] == 0 ){
return a;
}
if ( a->alf [ s[i]- 'a'] == 0 ){
a->alf[ s[i] - 'a' ] = new tries;
}
return ins( i + 1 , a->alf[ s[i]- 'a' ] );
}
queue <tries*> que;
void bfs ( ){
//t->fail = t ;
que.push ( tr );
while ( !que.empty() ){
tries *node = que.front();
que.pop();
for ( int i = 0 ; i < LENDIC ; i ++ ){
if ( node->alf[i] == NULL ){
continue ;
}
tries *temp = node->fail ;
while ( temp && temp->alf[i] == NULL ){
temp = temp->fail ;
}
if( temp == NULL ){
temp = tr ;
}else{
temp = temp->alf[i];
}
node->alf[i]->fail = temp;
temp->adj.push_back( node->alf[i] );
que.push( node->alf[i] );
}
}
}
int dfs( tries *nod ) {
vector < tries* > :: iterator it;
int nrsubarb = 0 ;
for ( it = nod->adj.begin() ; it != nod->adj.end() ; it++ ){
dfs( *it );
nod ->nrcuv += (*it)->nrcuv;
}
return nrsubarb ;
}
int main(){
int n;
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
scanf("%s",sircmp);
scanf("%d",&n);
for ( k = 0 ; k < n ; k ++ ){
scanf("%s", s);
sol[k] = ins( 0 , tr);
}
bfs ();
cur = tr;
for ( int i = 0 ; sircmp[ i ] ; i ++ ){
while ( cur && cur->alf[ sircmp [i] - 'a' ] == NULL ){
cur = cur->fail;
}
if( cur == NULL ){
cur = tr ;
}else {
cur = cur->alf[ sircmp[i] - 'a' ];
}
cur->nrcuv ++;
}
dfs( tr );
for ( int i = 0 ; i < n ; i++ ){
printf("%d\n", sol[i]->nrcuv );
}
return 0;
}