Pagini recente » Cod sursa (job #256236) | Cod sursa (job #2719566) | Cod sursa (job #2346030) | Cod sursa (job #978609) | Cod sursa (job #2523309)
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
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];
deque<trie *> c;
trie *adauga(trie *r, char *s)
{
if (*s == 0)
return r;
if (r->f[*s-'a'] == NULL)
r->f[*s-'a'] = new trie;
return adauga(r->f[*s-'a'], 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()
{
fin >> A >> n;
for (i=1; i<=n; i++)
{
fin >> s;
w[i] = adauga(root, s);
}
c.push_back(root);
while (!c.empty())
{
trie *nod = c.front(); c.pop_front();
for (i=0; i<26; i++)
if (nod->f[i])
{
trie *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_back(nod->f[i]);
}
}
trie *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++)
fout << w[i]->sol << "\n";
return 0;
}