Pagini recente » Cod sursa (job #3248956) | Cod sursa (job #359321) | Cod sursa (job #2658433) | Cod sursa (job #1171969) | Cod sursa (job #1971307)
#include <bits/stdc++.h>
using namespace std;
char s[1000002];
ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
struct Trie
{
int nr;
Trie *fail;
Trie *child[27];
Trie ()
{
nr = 0;
fail = NULL;
for (int i = 1; i<=26; ++i)
child[i] = NULL;
}
};
Trie *radacina, *Capat[101], *Q[1000555];
void baga (Trie *& node, int indice)
{
char c;
c = fin.get();
if (c<'a' || c>'z')
{
Capat[indice] = node;
return;
}
int poz = c-'a'+1;
if (node->child[poz] == NULL)
node->child[poz] = new Trie();
baga(node->child[poz], indice);
}
int main()
{
radacina = new Trie();
fin >> (s+1);
int n;
fin >> n;
fin.get();
for (int i = 1; i<=n; ++i)
baga(radacina, i);
radacina->fail = radacina;
int p = 1;
int u = 1;
Q[p] = radacina;
while (p<=u)
{
Trie *node = Q[p];
for (int i = 1; i<=26; ++i)
{
if (node->child[i] == NULL) continue;
Trie *suf = node->fail;
while (suf->child[i] == NULL && suf!=radacina)
suf = suf->fail;
if (suf->child[i]!=NULL && suf->child[i] != node->child[i])
node->child[i]->fail = suf->child[i];
else node->child[i]->fail = radacina;
Q[++u] = node->child[i];
}
++p;
}
int copie = n;
n = strlen(s+1);
Trie *unde = radacina;
for (int i = 1; i<=n; ++i)
{
int poz = s[i]-'a'+1;
while (unde!=radacina && unde->child[poz]==NULL)
unde = unde->fail;
if (unde->child[poz]!=NULL)
unde = unde->child[poz];
unde->nr++;
}
for (int i = u; i>=1; --i)
Q[i]->fail->nr+=Q[i]->nr;
for (int i = 1; i<=copie; ++i)
fout << Capat[i]->nr << '\n';
return 0;
}