Pagini recente » Cod sursa (job #969583) | Monitorul de evaluare | Cod sursa (job #604643) | Cod sursa (job #2642907) | Cod sursa (job #1954636)
#include <bits/stdc++.h>
#define MAXA 1000000
#define MAXB 10000
#define SIGMA 26
FILE *fi,*fout;
char A[MAXA+1];
char B[MAXB+2];
inline int read(char *str){
char ch=fgetc(fi);
while(!isalpha(ch))
ch=fgetc(fi);
int sz=0;
while(isalpha(ch)){
str[++sz]=ch;
ch=fgetc(fi);
}
return sz;
}
struct Aho{
Aho *son[SIGMA];
Aho *fail;
std::vector <int> poz;
int cnt;
Aho(){
memset(son,0,sizeof(son));
fail=0;
cnt=0;
}
};
Aho *root=new Aho;
void Insert(Aho *nod,char *str,int pos){
if(*str==-1)
nod->poz.push_back(pos);
else{
char ch=*str-'a';
if(nod->son[ch]==0)
nod->son[ch]=new Aho;
Insert(nod->son[ch],str+1,pos);
}
}
Aho *Q[MAXA+1];
int e;
inline void bfs(){
int b=0;
e=1;
root->fail=root;
Q[0]=root;
while(b<e){
Aho *nod=Q[b];
b++;
for(int i=0;i<SIGMA;i++)
if(nod->son[i]){
Aho *x=nod->fail;
while(x!=root&&x->son[i]==0)
x=x->fail;
if(x->son[i]!=nod->son[i]&&x->son[i])
nod->son[i]->fail=x->son[i];
else
nod->son[i]->fail=x;
Q[e++]=nod->son[i];
}
}
}
int n;
inline void solve(){
Aho *nod=root;
for(int i=1;i<=n;i++){
char ch=A[i]-'a';
if(nod->son[ch]==0)
while(nod!=root&&nod->son[ch]==0)
nod=nod->fail;
if(nod->son[ch]){
nod=nod->son[ch];
nod->cnt++;
}
}
}
int sol[MAXB+1];
inline void antibfs(){
for(int i=e-1;i>0;i--){
Aho *nod=Q[i];
for(int j=0;j<nod->poz.size();j++)
sol[nod->poz[j]]=nod->cnt;
if(nod->fail!=nod)
nod->fail->cnt+=nod->cnt;
}
}
int main(){
int i,m;
fi=fopen("ahocorasick.in" ,"r");
fout=fopen("ahocorasick.out" ,"w");
n=read(A);
fscanf(fi,"%d " ,&m);
for(i=1;i<=m;i++){
int sz=read(B);
B[sz+1]=-1;
Insert(root,B+1,i);
}
bfs();
solve();
antibfs();
for(i=1;i<=m;i++)
fprintf(fout,"%d\n" ,sol[i]);
fclose(fi);
fclose(fout);
return 0;
}