Cod sursa(job #2729728)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 25 martie 2021 10:38:17
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");

const int sigma = 26;
const int max_c = (int)1e4 + 5;
const int max_n = (int)1e6 + 5;

struct Trie {
  Trie *child[sigma];
  Trie *fail;
  vector<int> words;
  int cnt;
  Trie () {
    fail = nullptr;
    for (int i = 0; i < sigma; ++i) {
      child[i] = nullptr;
    }
    cnt = 0;
  }
};

int n, m;

char s[max_n];

char c[max_c];

Trie *root = new Trie();

int sol[max_c];

void insert(Trie *root, char *s, int id) {
  Trie *p = root;
  while (s[0] != '\0') {
    if (p -> child[s[0] - 'a'] == nullptr) {
      p -> child[s[0] - 'a'] = new Trie();
    }
    p = p -> child[s[0] - 'a'];
    s++;
  }
  p -> words.push_back(id);
}

void aho() {
  queue<Trie *> q;
  root -> fail = nullptr;
  for (int i = 0; i < sigma; ++i) {
    if (root -> child[i] != nullptr) {
      root -> child[i] -> fail = root;
      q.push(root -> child[i]);
    }
  }
  while ((int)q.size() > 0) {
    Trie *parrent = q.front();
    q.pop();
    for (int i = 0; i < sigma; ++i) {
      if (parrent -> child[i] != nullptr) {
        q.push(parrent -> child[i]);
        Trie *aux = parrent -> fail;
        while (aux != root && aux -> child[i] == nullptr) {
          aux = aux -> fail;
        }
        if (aux -> child[i] != nullptr) {
          parrent -> child[i] -> fail = aux -> child[i];
        } else {
          parrent -> child[i] -> fail = root;
        }
      }
    }
  }
}

void solve(char *s) {
  Trie *u = root;
  while (s[0] != '\0') {
    while (u != root && u -> child[s[0] - 'a'] == nullptr) {
      u = u -> fail;
    }
    if (u -> child[s[0] - 'a'] != nullptr) {
      u = u -> child[s[0] - 'a'];
    }
    u -> cnt++;
    s++;
  }
  queue<Trie *> q;
  q.push(root);
  vector<Trie *> antibfs;
  while ((int)q.size() > 0) {
    Trie *parrent = q.front();
    q.pop();
    antibfs.push_back(parrent);
    for (int i = 0; i < sigma; ++i) {
      if (parrent -> child[i] != nullptr) {
        q.push(parrent -> child[i]);
      }
    }
  }
  reverse(antibfs.begin(), antibfs.end());
  for (Trie *u : antibfs) {
    for (int i : u -> words) {
      sol[i] += u -> cnt;
    }
    if (u -> fail != nullptr) {
      u -> fail -> cnt += u -> cnt;
    }
  }
}

int main() {
  in >> (s + 1) >> n;
  for (int i = 1; i <= n; ++i) {
    in >> c;
    insert(root, c, i);
  }
  aho();
  solve(s + 1);
  for (int i = 1; i <= n; ++i) {
    out << sol[i] << "\n";
  }
  return 0;
}