Pagini recente » Cod sursa (job #102343) | Cod sursa (job #1694837) | Cod sursa (job #3203944) | Cod sursa (job #2074772) | Cod sursa (job #2334247)
# include <fstream>
# include <cstring>
# include <queue>
# include <vector>
# define DIMA 1000010
# define DIMB 10010
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct trie{
int val,sol;
vector<trie *> v;
trie *nx[26],*back;
trie(){
val=sol=0;
back=NULL;
for(int i=0;i<26;i++)
nx[i]=NULL;
}
} *tata,*nc,*nv,*prefix;
queue<trie *> q;
char b[105][DIMB],a[DIMA];
int n,m,i,r;
void adauga(trie *nod, char *s){
if(*s==NULL)
return;
if(nod->nx[*s-'a']==NULL)
nod->nx[*s-'a']=new trie;
adauga(nod->nx[*s-'a'],s+1);
}
int solutie(trie *nod,char *s){
if(*s==NULL)
return nod->sol;
return solutie(nod->nx[*s-'a'],s+1);
}
void dfs(trie *nod){
for(int i=0;i<nod->v.size();i++){
trie *nv;
nv=nod->v[i];
dfs(nv);
nod->sol+=nv->sol;
}
}
int main () {
tata=new trie;
fin>>a>>n;
m=strlen(a);
for(i=1;i<=n;i++){
fin>>b[i];
adauga(tata,b[i]);
}
q.push(tata);
while(!q.empty()){
r++;
nc=q.front();
nc->val=r;
q.pop();
for(i=0;i<26;i++){
nv=nc->nx[i];
if(nv==NULL)
continue;
q.push(nv);
prefix=nc->back;
while(prefix!=NULL&&prefix->nx[i]==NULL)
prefix=prefix->back;
if(prefix==NULL){
prefix=tata;
}
else{
if(prefix->nx[i]!=NULL)
prefix=prefix->nx[i];
}
nv->back=prefix;
prefix->v.push_back(nv);
}
}
prefix=tata;
for(i=0;i<m;i++){
while(prefix!=tata&&prefix->nx[a[i]-'a']==NULL)
prefix=prefix->back;
if(prefix->nx[a[i]-'a']!=NULL)
prefix=prefix->nx[a[i]-'a'];
prefix->sol++;
}
dfs(tata);
for(i=1;i<=n;i++)
fout<<solutie(tata,b[i])<<"\n";
return 0;
}