Pagini recente » Cod sursa (job #56163) | Cod sursa (job #2857637) | Cod sursa (job #2503468) | Cod sursa (job #641485) | Cod sursa (job #2446722)
#include <bits/stdc++.h>
using namespace std;
const int ALPHA = 26;
#define pb push_back
struct Node {
int nxt[ALPHA];
int val;
int fail;
};
const int N = 100;
string t, s[1 + N];
struct Ahoi {
vector <Node> trie;
vector <int> f;
int cnt;
Ahoi (int l, int n) {
trie.resize (1 + l);
f.resize (1 + n);
cnt = 0;
}
void ins (int node, int ind, int p) {
if (p == s[ind].size()) {
f[ind] = node;
return;
}
if (!trie[node].nxt[s[ind][p] - 'a'])
trie[node].nxt[s[ind][p] - 'a'] = ++cnt;
ins (trie[node].nxt[s[ind][p] - 'a'], ind, p + 1);
}
vector <int> ord;
void fail () {
queue <int> q;
for (int i = 0; i < ALPHA; i++)
if (trie[0].nxt[i])
q.push (trie[0].nxt[i]);
while (!q.empty ()) {
int node = q.front ();
q.pop ();
ord.pb (node);
for (int i = 0; i < ALPHA; i++)
if (trie[node].nxt[i]) {
int vec = trie[node].nxt[i];
q.push (vec);
trie[vec].fail = trie[node].fail;
while (trie[vec].fail && !trie[trie[vec].fail].nxt[i])
trie[vec].fail = trie[trie[vec].fail].fail;
if (trie[trie[vec].fail].nxt[i])
trie[vec].fail = trie[trie[vec].fail].nxt[i];
}
}
}
void get_val () {
int node = 0;
for (int i = 0; i < t.size (); i++){
while (node && !trie[node].nxt[t[i] - 'a'])
node = trie[node].fail;
if (trie[node].nxt[t[i] - 'a'])
node = trie[node].nxt[t[i]-'a'];
trie[node].val++;
}
}
void prop () {
reverse (ord.begin (), ord.end ());
for (auto node : ord)
trie[trie[node].fail].val += trie[node].val;
}
};
int main() {
int n;
freopen ("ahocorasick.in", "r", stdin);
freopen ("ahocorasick.out", "w", stdout);
cin >> t;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> s[i];
Ahoi dic (t.size (), n);
for (int i = 1; i <= n; i++)
dic.ins (0, i, 0);
dic.fail (); dic.get_val (); dic.prop ();
for (int i = 1; i <= n; i++)
cout << dic.trie[dic.f[i]].val << "\n";
return 0;
}