Cod sursa(job #2641837)

Utilizator segtreapMihnea Andreescu segtreap Data 12 august 2020 20:27:51
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Trie {
  Trie *kids[26];
  Trie *fail;
  int f;
  vector<int> v;
  string s;
  Trie() {
    for (int j = 0; j < 26; j++) {
      kids[j] = 0;
    }
    s = "";
    fail = 0;
    f = 0;
    v.clear();
  }
};

Trie *root = new Trie;
int n;
string s;
string t;
vector<Trie*> ord;

void build_fail() {
  for (auto &now : ord) {
    for (int x = 0; x < 26; x++) {
      if (now->kids[x]) {
        Trie *cur = now->fail;
        while (cur != root && !cur->kids[x]) {
          cur = cur->fail;
        }
        if (now != root && cur->kids[x]) {
          cur = cur->kids[x];
        }
        now->kids[x]->fail = cur;
      }
    }
  }
}

void calc_order() {
  queue<Trie*> q;
  q.push(root);
  while (!q.empty()) {
    Trie *now = q.front();
    ord.push_back(now);
    q.pop();
    for (int x = 0; x < 26; x++) {
      if (now->kids[x]) {
        q.push(now->kids[x]);
      }
    }
  }
}

int main() {
  freopen ("ahocorasick.in", "r", stdin);
  freopen ("ahocorasick.out", "w", stdout);
  cin >> s >> n;
  vector<int> ans(n);
  for (int i = 1; i <= n; i++) {
    cin >> t;
    Trie *now = root;
    for (auto &ch : t) {
      int x = ch - 'a';
      if (!now->kids[x]) {
        now->kids[x] = new Trie;
        now->kids[x]->s = now->s + ch;
      }
      now = now->kids[x];
    }
    now->v.push_back(i - 1);
  }
  root->fail = root;
  calc_order();
  build_fail();
  Trie *now = root;
  for (auto &ch : s) {
    int x = ch - 'a';
    while (now != root && !now->kids[x]) {
      now = now->fail;
    }
    if (now->kids[x]) {
      now = now->kids[x];
    }
    now->f++;
  }
  reverse(ord.begin(), ord.end());
  for (auto &it : ord) {
    it->fail->f += it->f;
    for (auto &j : it->v) {
      ans[j] += it->f;
    }
  }
  for (auto &x : ans) {
    cout << x << "\n";
  }
  return 0;
}