Pagini recente » Cod sursa (job #2237740) | Cod sursa (job #2822524) | Cod sursa (job #1094628) | Cod sursa (job #1793478) | Cod sursa (job #1305570)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define dt 1000005
#define dc 10005
char text[dt],cuv[dc];
int n ,inc , fin ;
int sum[dc];
struct trie{
trie *fiu[26],*fail;
int n0;
vector<int> v;
trie(){
memset(fiu,0,sizeof(fiu));
fail = NULL;
n0 = 0;
}
};
trie *t = new trie , *q[dc*dc],*p;
void insert( trie *nod , char *c , int i ){
if( *c == '\0' ){
nod->v.push_back(i);
return ;
}
int urm = *c - 'a';
if( nod->fiu[urm] == 0 ) nod->fiu[urm] = new trie;
insert(nod->fiu[urm] , c+1, i );
}
void bfs(trie *nod){
trie *fail,*tmp;
nod->fail = nod;
for( q[ inc = fin = 1 ] = nod;inc <= fin ;++inc ){
tmp = q[inc];
for(int i=0;i<26;++i)
if( tmp->fiu[i] != NULL ){
for( fail = tmp->fail; fail != nod && fail->fiu[i] == NULL; fail = fail->fail );
if( fail->fiu[i] != NULL && fail->fiu[i] != tmp->fiu[i] ) fail = fail->fiu[i];
tmp->fiu[i]->fail = fail;
q[++fin] = tmp->fiu[i];
}
}
nod->fail = NULL;
}
void antibfs(){
trie *tmp;
for(int i=fin; i ; --i){
tmp = q[i];
if( tmp->fail != NULL ) tmp->fail->n0 += tmp->n0;
for(int j=0; j < tmp->v.size(); ++j) sum[ tmp->v[j] ] = tmp->n0;
}
}
int main()
{
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
scanf("%s",text);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%s",cuv);
insert(t,cuv,i);
}
bfs(t);
p = t;
int len = strlen(text);
for(int i = 0; i < len; ++i){
int urm = text[i] - 'a';
for( ; p->fiu[urm]==NULL && p!=t ; p = p->fail);
if( p->fiu[urm] != NULL ) p = p->fiu[urm];
++p->n0;
}
antibfs();
for(int i=1; i<=n; ++i) printf("%d\n",sum[i]);
return 0;
}