Pagini recente » cerculdeinfo-lectia14-cautare_binara | Cod sursa (job #1029265) | Cod sursa (job #2530008) | Cod sursa (job #152225) | Cod sursa (job #2187592)
#include <bits/stdc++.h>
using namespace std;
const int sigma = 26;
const int nmax = 100 + 10;
string s_to_update;
struct trie {
int cnt;
trie *phi;
trie *son[sigma];
trie() {
cnt = 0; phi = NULL;
for (int i = 0; i < sigma; ++i)
son[i] = NULL;
}
trie *update(int pos) {
if (pos == s_to_update.size()) {
return this;
}
int to = s_to_update[pos] - 'a';
if (son[to] == NULL)
son[to] = new trie;
return son[to] -> update(pos + 1);
}
};
trie *whr[nmax];
class aho_corasick {
trie *root = new trie;
int dmax = 10, dim = 0;
trie **q;
public:
void add(string s, int idx) {
s_to_update = s;
dmax += s.size();
whr[idx] = root -> update(0);
}
void compute_phi() {
q = new trie *[dmax];
q[++dim] = root; root -> phi = root;
for (int i = 1; i <= dim; ++i) {
trie *node = q[i];
for (int to = 0; to < sigma; ++to) {
if (node -> son[to] == NULL)
continue;
trie *k = node -> phi;
while (k != root && k -> son[to] == NULL)
k = k -> phi;
if (k != node && k -> son[to] != NULL)
k = k -> son[to];
node -> son[to] -> phi = k;
q[++dim] = node -> son[to];
}
}
}
void compute_ans(string S) {
trie *k = root;
for (int i = 0; i < S.size(); ++i) {
int to = S[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;
}
};
string str, s;
int n;
aho_corasick ac;
int main() {
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
ios_base :: sync_with_stdio(false);
cin >> str;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> s;
ac.add(s, i);
}
ac.compute_phi();
ac.compute_ans(str);
for (int i = 1; i <= n; ++i)
cout << whr[i] -> cnt << '\n';
return 0;
}