Cod sursa(job #2664847)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 29 octombrie 2020 16:12:59
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

struct trie {
  trie *k[26];
  trie *f;
  int sol;
  vector<int> who;
  trie() {
    sol = 0;
    f = 0;
    for (int i = 0; i < 26; i++) {
      k[i] = 0;
    }
  }
};

trie *root = new trie;
const int N = 100 + 7;
int sol[N];
vector<trie*> ord;

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


void fo() {
  queue<trie*> q;
  q.push(root);
  while (!q.empty()) {
    trie* cur = q.front();
    ord.push_back(cur);
    q.pop();
    for (int x = 0; x < 26; x++) {
      if (cur->k[x]) {
        q.push(cur->k[x]);
      }
    }
  }
  for (auto &cur : ord) {
    for (int x = 0; x < 26; x++) {
      if (cur->k[x]) {
        trie *now = cur->k[x];
        if (cur == root) {
          now->f = root;
        } else {
          now->f = cur->f;
          while (now->f != root && !now->f->k[x]) {
            now->f = now->f->f;
          }
          if (now->f->k[x]) {
            now->f = now->f->k[x];
          }
        }
      }
    }
  }
}

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

  string s;
  int dw;
  cin >> s >> dw;
  for (int i = 1; i <= dw; i++) {
    string t;
    cin >> t;
    ins(t, i);
  }
  root->f = root;
  fo();
  trie *cur = root;
  for (auto &c : s) {
    int x = c - 'a';
    while (cur != root && !cur->k[x]) {
      cur = cur->f;
    }
    if (cur->k[x]) {
      cur = cur->k[x];
    }
    cur->sol++;
  }
  reverse(ord.begin(), ord.end());
  for (auto &x : ord) {
    x->f->sol += x->sol;
  }
  for (auto &x : ord) {
    for (auto &i : x->who) {
      sol[i] = x->sol;
    }
  }
  for (int i = 1; i <= dw; i++) {
    cout << sol[i] << "\n";
  }
}