Pagini recente » Cod sursa (job #1782394) | Cod sursa (job #1825064) | Cod sursa (job #2720843) | Cod sursa (job #255628) | Cod sursa (job #1813845)
#include <bits/stdc++.h>
using namespace std;
const int sigma = 26;
const int nmax = 1e2 + 10;
const int lmax = 1e4 + 10;
const int dmax = nmax * lmax;
struct trie {
trie *phi, *son[sigma];
int cnt;
trie() {
phi = NULL;
for (int i = 0; i < sigma; ++i) son[i] = NULL;
cnt = 0;
}
};
string str, s;
int dim, n;
trie *q[dmax];
trie *root, *whr[nmax];
trie *add(trie *node, int pos) {
if (pos == (int)s.size())
return node;
int to = s[pos] - 'a';
if (node -> son[to] == NULL)
node -> son[to] = new trie;
return add(node -> son[to], pos + 1);
}
void compute_phi() {
root -> phi = root;
q[++dim] = root;
for (int it = 1; it <= dim; ++it) {
trie *node = q[it];
for (int i = 0; i < sigma; ++i) {
if (node -> son[i] == NULL) continue;
trie *k = node -> phi;
while (k != root && k -> son[i] == NULL)
k = k -> phi;
if (k -> son[i] != NULL && k != node) k = k -> son[i];
node -> son[i] -> phi = k;
q[++dim] = node -> son[i];
}
}
}
void compute_aho() {
trie *k = root;
for (int i = 0; i < (int)str.size(); ++i) {
int to = str[i] - 'a';
while (k != root && k -> son[to] == NULL)
k = k -> phi;
if (k -> son[to] != NULL) k = k -> son[to];
k -> cnt++;
}
for (int i = dim; i ; --i)
q[i] -> phi -> cnt += q[i] -> cnt;
}
int main()
{
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
root = new trie;
fin >> str;
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> s;
whr[i] = add(root, 0);
}
compute_phi();
compute_aho();
for (int i = 1; i <= n; ++i)
fout << whr[i] -> cnt << '\n';
return 0;
}