Pagini recente » Cod sursa (job #1169231) | Cod sursa (job #1061183) | Cod sursa (job #150606) | Cod sursa (job #789686) | Cod sursa (job #2409672)
#include <bits/stdc++.h>
using namespace std;
const int SIGMA = 26;
const int NMAX = 1000005;
const int MMAX = 10005;
const int QMAX = 105;
struct Node
{
Node *son[SIGMA], *suffLink;
int cnt; vector<Node*> edg;
Node (Node *_to = NULL)
{
suffLink = NULL; cnt = 0;
for (int i = 0; i < SIGMA; ++i) {
son[i] = _to; }
}
};
Node *root, *nil; deque<Node*> que;
char str[NMAX], aux[QMAX][MMAX];
void add(Node *&node, char *str, int l, int p = 1)
{
if (node == nil) {
node = new Node(nil); }
if (p == l + 1) {
return; }
add(node -> son[str[p] - 'a'], str, l, p + 1);
}
void build_aho(Node *root) {
for (que.assign(1, root); que.size(); que.pop_front()) {
Node *node = que.front();
for (int i = 0; i < SIGMA; ++i) {
if (node -> son[i] != nil) {
Node *aux = node -> suffLink;
while (aux != NULL && aux -> son[i] == nil) {
aux = aux -> suffLink; }
if (aux == NULL) {
node -> son[i] -> suffLink = root; }
else {
node -> son[i] -> suffLink = aux -> son[i]; }
(node -> son[i] -> suffLink -> edg).push_back(node -> son[i]);
que.push_back(node -> son[i]); } } }
}
void dfs(Node *node)
{
for (Node *next : node -> edg) {
dfs(next); node -> cnt += next -> cnt; }
}
void run_aho(Node *root, char *str, int n)
{
Node *node = root;
for (int i = 1; i <= n; ++i) {
while (node != root && node -> son[str[i] - 'a'] == nil) {
node = node -> suffLink; }
if (node -> son[str[i] - 'a'] != nil) {
node = node -> son[str[i] - 'a']; }
++node -> cnt; }
dfs(root);
}
int query(Node *node, char *str, int l, int p = 1)
{
if (p == l + 1) {
return node -> cnt; }
else {
return query(node -> son[str[p] - 'a'], str, l, p + 1); }
}
int main(void)
{
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
cin >> (str + 1);
int n = (int) strlen(str + 1);
int q; cin >> q;
root = nil = new Node();
for (int i = 0; i < SIGMA; ++i) {
nil -> son[i] = nil; }
for (int i = 1; i <= q; ++i) {
cin >> (aux[i] + 1);
add(root, aux[i], (int) strlen(aux[i] + 1)); }
build_aho(root); run_aho(root, str, n);
for (int i = 1; i <= q; ++i) {
cout << query(root, aux[i], (int) strlen(aux[i] + 1)) << "\n"; }
return 0;
}