Pagini recente » Cod sursa (job #2030593) | Cod sursa (job #534730) | Cod sursa (job #2961156) | Cod sursa (job #1775475) | Cod sursa (job #2523372)
#include <fstream>
#include <vector>
#include <queue>
#define fiu f[*s-'a']
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],*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++)
{
dfs(nod->v[i]);
nod->sol += nod->v[i]->sol;
}
}
int main()
{
fin >> A >> n;
for (i=1; i<=n; i++)
{
fin >> 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++)
fout << w[i]->sol << "\n";
return 0;
}