Pagini recente » Cod sursa (job #245895) | Cod sursa (job #2016737) | Cod sursa (job #2728343) | Cod sursa (job #310083) | Cod sursa (job #1719818)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cstring>
#include <string>
using namespace std;
struct Trie{
Trie *next[26],*fail;
vector<int> ind;
int cnt;
Trie(){
memset(next,0,sizeof(next));
fail=NULL,cnt=0;
}
};
Trie *root=new Trie(),*q[500000];
int N,M,L,ans[110],K;
string A,B;
void ins(Trie *&nod, int k, int ind){
if (nod==NULL) nod=new Trie();
if (k>=L){
nod->ind.push_back(ind);
return;
}
ins(nod->next[B[k]-'a'],k+1,ind);
}
void calc_fail(){
Trie *aux,*nod; root->fail=root;
K=1,q[1]=root;
int i,j;
for (i=1; i<=K; i++){
nod=q[i];
for (j=0; j<26; j++)
if (nod->next[j]!=NULL){
aux=nod->fail;
while (aux->next[j]==NULL && aux!=root) aux=aux->fail;
nod->next[j]->fail=aux->next[j];
if (aux->next[j]==NULL || aux==nod) nod->next[j]->fail=root;
q[++K]=nod->next[j];
}
}
}
void rbfs(){
int i,j; Trie *nod;
for (i=K; i>0; i--){
nod=q[i];
nod->fail->cnt+=nod->cnt;
for (j=0; j<nod->ind.size(); j++)
ans[nod->ind[j]]=nod->cnt;
}
}
int main(){
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
fin >> A;
fin >> M;
int i;
N=A.length();
for (i=1; i<=M; i++){
fin >> B;
L=B.length();
ins(root,0,i);
}
calc_fail();
Trie *cr=root;
for (i=0; i<N; i++){
while (cr!=root && cr->next[A[i]-'a']==NULL)
cr=cr->fail;
if (cr->next[A[i]-'a']) cr=cr->next[A[i]-'a'];
cr->cnt++;
}
rbfs();
for (i=1; i<=M; i++) fout << ans[i] << "\n";
return 0;
}