Pagini recente » Cod sursa (job #2370416) | Cod sursa (job #1418617) | Cod sursa (job #2124438) | Cod sursa (job #190451) | Cod sursa (job #2067108)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct ac{
vector <int> ind;
ac* son[26];
ac* fail;
int nr;
ac(){
memset(son,0,sizeof(son));
fail = 0;
nr = 0;
}
};
ac *t = new ac();
int N,K;
char S[1000005];
char c[10005];
ac *Q[100000005];
int sol[1000005];
void add(ac* nod,char* s,int index){
if(!isalpha(*s)){
nod->ind.push_back(index);
return;
}
if(nod->son[*s-'a']==0){
nod->son[*s-'a'] = new ac();
}
add(nod->son[*s-'a'],s+1,index);
}
void BFS(){
t->fail = t;
Q[++K] = t;
for(int i=1;i<=K;i++){
ac* nod = Q[i];
for(int j=0;j<26;j++){
ac* son = nod->son[j];
if(son==0) continue;
ac* cf = nod->fail;
while(cf->son[j]==0 && cf!=t) cf = cf->fail;
if(cf == t && t->son[j]==0)
son->fail = t;
else
son->fail = cf->son[j];
if(son->fail == son)
son->fail = t;
Q[++K] = son;
}
}
t->fail=0;
}
void ABFS(){
for(int i=K;i>0;i--){
ac* nod = Q[i];
if(nod->fail)
nod->fail->nr+=nod->nr;
for(int j=0;j<nod->ind.size();j++)
sol[nod->ind[j]] = nod->nr;
}
}
void solve(){
ac* nod = t;
for(int i=0;S[i];i++){
int c = S[i]-'a';
while(nod->son[c]==0 && nod!=t) nod = nod->fail;
if(nod->son[c]){
nod=nod->son[c];
nod->nr++;
}
}
}
int main()
{
fin>>S;
fin>>N;
for(int i=1;i<=N;i++)
{
fin>>c;
add(t,c,i);
}
BFS();
solve();
ABFS();
for(int i=1;i<=N;i++){
fout<<sol[i]<<"\n";
}
return 0;
}