Cod sursa(job #2593014)

Utilizator segtreapMihnea Andreescu segtreap Data 2 aprilie 2020 18:20:33
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Trie {
  vector<int> id;
  Trie *kids[26];
  Trie *fail;
  int sol;
  Trie() {
    id.clear();
    for (int i = 0; i < 26; i++) {
      kids[i] = 0;
    }
    fail = 0;
    sol = 0;
  }
};

Trie *root = new Trie;

void ins(string s, int i) {
  Trie *now = root;
  for (auto &c : s) {
    int x = c - 'a';
    if (!now->kids[x]) {
      now->kids[x] = new Trie;
    }
    now = now->kids[x];
  }
  now->id.push_back(i);
}

vector<Trie*> ord;

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

int sol[107];

int main() {
  freopen ("ahocorasick.in", "r", stdin);
  freopen ("ahocorasick.out", "w", stdout);

  string s;
  cin >> s;
  int m;
  cin >> m;
  for (int i = 1; i <= m; i++) {
    string t;
    cin >> t;
    ins(t, i);
  }
  build();
  Trie *now = root;
  for (auto &c : s) {
    int x = c - 'a';
    while (now != root && !now->kids[x]) {
      now = now->fail;
    }
    if (now->kids[x]) {
      now = now->kids[x];
    }
    now->sol++;
  }
  reverse(ord.begin(), ord.end());
  for (auto &now : ord) {
    for (auto &i : now->id) {
      sol[i] += now->sol;
    }
    now->fail->sol += now->sol;
  }
  for (int i = 1; i <= m; i++) {
    cout << sol[i] << "\n";
  }
}