Cod sursa(job #2409672)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 19 aprilie 2019 12:37:40
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.35 kb
#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;
}