Pagini recente » Cod sursa (job #2482963) | Cod sursa (job #1901620) | Cod sursa (job #1305180) | Cod sursa (job #2872913) | Cod sursa (job #2523381)
#include <cstdio>
#include <vector>
#include <queue>
#define fiu f[*s-'a']
using namespace std;
FILE *fin = fopen("ahocorasick.in", "r");
FILE *fout = fopen("ahocorasick.out", "w");
int n,i;
char A[1000005],s[10005];
struct trie{
int sol;
trie *f[26];
trie *back;
vector<trie *> v;
trie ()
{
sol = 0;
for (int i=0; i<26; ++i)
f[i] = 0;
back = 0;
v.clear();
}
};
trie *root = new trie();
trie *w[105],*nod,*aux;
queue<trie *> c;
trie *adauga(trie *r, char *s)
{
if (*s == 0)
return r;
if (r->fiu == NULL)
r->fiu = new trie;
return adauga(r->fiu, s+1);
}
void dfs(trie *nod)
{
for (int i=0; i<nod->v.size(); ++i)
{
trie *vecin = nod->v[i]; dfs(vecin);
nod->sol += vecin->sol;
}
}
int main()
{
fscanf(fin, "%s", &A); fscanf(fin, "%d", &n);
for (i=1; i<=n; ++i)
{
fscanf(fin, "%s", &s);
w[i] = adauga(root, s);
}
c.push(root);
while (!c.empty())
{
nod = c.front(); c.pop();
for (i=0; i<26; ++i)
if (nod->f[i])
{
aux = nod->back;
while (aux && aux->f[i] == NULL)
aux = aux->back;
if (aux == 0)
nod->f[i]->back = root;
else
nod->f[i]->back = aux->f[i];
nod->f[i]->back->v.push_back(nod->f[i]);
c.push(nod->f[i]);
}
}
aux = root;
for (i=0; A[i]!=0; ++i)
{
while (aux != root && aux->f[A[i]-'a'] == NULL)
aux = aux->back;
if (aux->f[A[i]-'a'] != NULL)
aux = aux->f[A[i]-'a'];
aux->sol++;
}
dfs(root);
for (i=1; i<=n; ++i)
fprintf(fout, "%d\n", w[i]->sol);
return 0;
}