Pagini recente » Cod sursa (job #1658653) | Cod sursa (job #877485) | Cod sursa (job #2379333) | Cod sursa (job #2889770) | Cod sursa (job #1220788)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
char a[1000010],s[10010];
int n,i;
struct trie {
int nr;
trie *f[26],*back;
vector <trie*> v;
trie () {
nr=0;
back=0;
for (i=0;i<26;i++)
f[i]=0;
}
} *r= new trie, *nod, *aux, *w[110];
queue <trie*> q;
trie *update (trie *nod, char *p) {
if (*p==0)
return nod;
if (nod->f[*p-'a']==0)
nod->f[*p-'a']=new trie;
return update(nod->f[*p-'a'], p+1);
}
void dfs (trie *nod) {
for (int i=0;i<nod->v.size();i++) {
dfs(nod->v[i]);
nod->nr+=nod->v[i]->nr;
}
}
int main () {
fin>>a;
fin>>n;
for (int i=1;i<=n;i++) {
fin>>s;
w[i]=update (r,s);
}
q.push(r);
while (!q.empty()){
nod = q.front();
q.pop();
for (i=0;i<26;i++) {
if (nod->f[i]!=0) {
q.push (nod->f[i]);
aux=nod->back;
while (aux && !aux->f[i])
aux=aux->back;
if (!aux)
nod->f[i]->back=r;
else
nod->f[i]->back=aux->f[i];
nod->f[i]->back->v.push_back(nod->f[i]);
}
}
}
for (i=0 , aux=r;i<strlen(a);i++){
while (aux && !aux->f[a[i]-'a'])
aux=aux->back;
if (!aux)
aux=r;
else
aux=aux->f[a[i]-'a'];
aux->nr++;
}
dfs(r);
for (i=1;i<=n;i++)
fout<< w[i]->nr <<"\n";
return 0;
}