Pagini recente » Cod sursa (job #2459903) | Cod sursa (job #2378479) | Cod sursa (job #2745678) | Cod sursa (job #790120) | Cod sursa (job #1673935)
# include <bits/stdc++.h>
# define NR 1000005
# define L 10005
# define sigma 26
# define CH (*s - 'a')
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
struct trie {
int nr; //numarul de potriviri
trie *fiu[sigma], *fail;
vector <trie*> adj;
trie() {
nr=0; fail=NULL;
memset (fiu, 0, sizeof(fiu));
adj.clear();
}
}*poz[105];
trie *T=new trie;
int i,j,n,m;
char s[NR], var[L];
trie *ins (trie *nod, char *s) {
if (*s=='\0') return nod;
if (nod->fiu[CH]==NULL)
nod->fiu[CH] = new trie;
return ins (nod->fiu[CH], s+1);
}
void BFS () {
queue <trie*> q;
q.push(T);
while (! q.empty()) {
trie *nod=q.front(); q.pop();
for (int i=0; i<26; ++i) {
if (nod->fiu[i]==NULL) continue;
trie *aux=nod->fail;
while (aux!=NULL && aux->fiu[i]==NULL)
aux=aux->fail;
if (aux==NULL) aux=T;
else aux=aux->fiu[i];
nod->fiu[i]->fail = aux;
aux->adj.push_back(nod->fiu[i]);
q.push(nod->fiu[i]);
}
}
}
void DFS (trie *nod) {
for (vector<trie*>::iterator adj = nod->adj.begin(); adj != nod->adj.end(); ++adj) {
DFS(*adj);
nod->nr += (*adj)->nr;
}
}
int main ()
{
f.getline (s+1, NR); n=strlen(s+1);
f>>m; f.get();
for (i=1; i<=m; ++i) {
f.getline (var+1, L);
poz[i]=ins (T, var+1);
}
BFS ();
trie *curr=T;
for (int i=1; i<=n; ++i) {
while (curr && curr->fiu[s[i]-'a']==NULL)
curr=curr->fail;
if (curr==NULL) curr=T;
else curr=curr->fiu[s[i]-'a'];
curr->nr ++;
}
DFS (T);
for (i=1; i<=m; ++i)
g<<poz[i]->nr<<"\n";
return 0;
}