Pagini recente » Cod sursa (job #72196) | Cod sursa (job #244207) | Cod sursa (job #484697) | Cod sursa (job #1645024) | Cod sursa (job #1730362)
#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;
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;
Q.push(R->leg[i]);
//d[++lg] = 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;
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];
++R->num;
}
//atac();
for(int i = 1; i <= q; ++i)
printf("%d\n",v[i]);
return 0;
}