Pagini recente » Cod sursa (job #2019877) | Cod sursa (job #460529) | Cod sursa (job #2037790) | Istoria paginii runda/gg/clasament | Cod sursa (job #2487186)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
struct Trie {
int nr;
Trie* fii[26];
Trie *fail;
Trie () {
nr = 0;
fail = NULL;
for (int i = 0; i < 26; i++)
fii[i] = NULL;
}
} *root, *Nod[102];
Trie* add (string s, int i) {
Trie* p = root;
for (int i = 0; i < s.size(); i++) {
if (p -> fii[s[i] - 'a'] == NULL)
p -> fii[s[i] - 'a'] = new Trie;
p = p -> fii[s[i] - 'a'];
}
Nod[i] = p;
return p;
}
void antiBFS (Trie *nod) {
for (int i = 0; i < 26; i++)
if (nod -> fii[i] != NULL)
antiBFS(nod -> fii[i]);
if (nod != root)
nod -> fail -> nr += nod -> nr;
}
int n;
string s, a;
int main()
{
fin >> s >> n;
root = new Trie;
for (int i = 1; i <= n; i++) {
fin >> a;
add(a, i);
}
queue<Trie*>q;
root -> fail = NULL;
for (int i = 0; i < 26; i++) {
if (root -> fii[i] != NULL) {
root -> fii[i] -> fail = root;
q.push(root -> fii[i]);
}
}
while (!q.empty()) {
Trie* nod = q.front();
q.pop();
for (int i = 0; i < 26; i++) {
if (nod -> fii[i] != NULL) {
q.push(nod -> fii[i]);
Trie* aux = nod -> fail;
while (aux != root && aux -> fii[i] == NULL)
aux = aux -> fail;
if (aux -> fii[i] != NULL)
nod -> fii[i] -> fail = aux -> fii[i];
else
nod -> fii[i] -> fail = root;
}
}
}
Trie* p = root;
for (int i = 0; i < s.size(); i++) {
while(p != root && p -> fii[s[i] - 'a'] == NULL)
p = p -> fail;
if (p -> fii[s[i] - 'a'] != NULL)
p = p -> fii[s[i] - 'a'];
else
p = root;
if (p != root)
p -> nr++;
}
antiBFS(root);
for (int i = 1; i <= n; i++)
fout << Nod[i] -> nr << "\n";
return 0;
}