Pagini recente » Cod sursa (job #2768097) | Cod sursa (job #3152224) | Cod sursa (job #2847181) | Cod sursa (job #3246387) | Cod sursa (job #1730384)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e6+2; const int cmax = 10005;
struct Trie{
Trie *leg[26],*fall;
vector<int>p;
int ok,num;
Trie(){
ok = num = 0;
fall = NULL;
for(int i = 0; i < 26; ++i)
leg[i] = NULL;
}
}*T,*d[10005];
queue<Trie*>Q;
char t[nmax],ch[cmax];
int q,N,v[105],lg;
inline void Init(Trie *R,int i,int cnt){
int x = ch[i]-'a';
if(R->leg[x] == NULL)
R->leg[x] = new Trie;
if(i == N-1) {R->leg[x]->p.push_back(cnt);return;}
Init(R->leg[x],i+1,cnt);
}
inline void Bfs(){
int i;
Trie *R,*F;
for(i = 0; i < 26; ++i)
if(T->leg[i])Q.push(T->leg[i]),T->leg[i]->fall = T,d[++lg] = T->leg[i];
while(!Q.empty()){
R = Q.front();
Q.pop();
for(i = 0; i < 26; ++i)
if(R->leg[i]){
F = R->fall;
while(F != T && F->leg[i] == NULL)F = F->fall;
if(F->leg[i])R->leg[i]->fall = F->leg[i];
else R->leg[i]->fall = T;
d[++lg] = R->leg[i];
Q.push(R->leg[i]);
}
}
}
inline void atac(){
Trie *R;
while(lg){
R = d[lg];
if(R->fall)R->fall->num+=R->num;
for(int i = 0; i < R->p.size();++i)v[R->p[i]] = R->num;
--lg;
}
}
int main(){
ios::sync_with_stdio(false);
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
scanf("%s\n%d\n",t,&q);
T = new Trie;
for(int i = 1; i <= q; ++i){
scanf("%s",ch); N = strlen(ch);
Init(T,0,i);
}
Bfs();
Trie* R = T,*F;
int x;
int g = strlen(t);
for(int i = 0; i < g; ++i){
x = t[i] - 'a';
while(R != T && R->leg[x] == NULL)R = R->fall;
if(R->leg[x])
R = R->leg[x];
++R->num;
}
atac();
for(int i = 1; i <= q; ++i)
printf("%d\n",v[i]);
return 0;
}