Pagini recente » Cod sursa (job #3140625) | Cod sursa (job #1744200) | Cod sursa (job #1372199) | Cod sursa (job #1668895) | Cod sursa (job #1730251)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e6+2; const int cmax = 10005;
struct Trie{
Trie *leg[26],*fall;
int ok;
Trie(){
ok = 0;
for(int i = 0; i < 26; ++i)
leg[i] = NULL;
}
}*T;
queue<Trie*>Q;
char t[nmax],ch[cmax];
int q,N,v[105];
inline void Init(Trie *T,int i,int cnt){
int x = ch[i]-'a';
if(T->leg[x]) {
if(i == N-1) {T->leg[x]->ok = true;return;}
Init(T->leg[x],i+1,cnt);
}
else{
T->leg[x] = new Trie;
if(i == N-1) {T->leg[x]->ok = cnt;return;}
Init(T->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;
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;
Q.push(R->leg[i]);
}
}
}
}
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;
for(int i = 0; i < strlen(t); ++i){
x = t[i] - 'a';
while(R != T && R->leg[x] == NULL)R = R->fall;
if(R->leg[x]){
R = R->leg[x];
if(R->ok) ++v[R->ok];
F = R;
while(F!=T){
if(F->fall->ok)++v[F->fall->ok];
F = F->fall;
}
}
else R = T;
}
for(int i = 1; i <= q; ++i)
printf("%d\n",v[i]);
return 0;
}