string/KMPA.cpp

• View this file on GitHub
• Last update: 2024-01-24 20:41:29+08:00

Code

struct KMPA {
  static constexpr array<int, 26> UNIT = {};
  vector<array<int, 26>> v;
  vector<int> pi;

  KMPA() {
    pi.emplace_back(0);
    v.emplace_back(UNIT);
  }

  void insert(char ch) {
    int id = ch - 'a';
    pi.emplace_back(v.back()[id]);
    v.back()[id] = ssize(v);
    v.emplace_back(UNIT);
    for(int i = 0; i < 26; i++)
      v.back()[i] = v[pi.back()][i];
  }

  void pop() {
    assert(ssize(v) > 1);
    v.pop_back();
    pi.pop_back();
    int id = ranges::max_element(v.back()) - v.back().begin();
    v.back()[id] = v[pi.back()][id];
  }
};

#line 1 "string/KMPA.cpp"
struct KMPA {
  static constexpr array<int, 26> UNIT = {};
  vector<array<int, 26>> v;
  vector<int> pi;

  KMPA() {
    pi.emplace_back(0);
    v.emplace_back(UNIT);
  }

  void insert(char ch) {
    int id = ch - 'a';
    pi.emplace_back(v.back()[id]);
    v.back()[id] = ssize(v);
    v.emplace_back(UNIT);
    for(int i = 0; i < 26; i++)
      v.back()[i] = v[pi.back()][i];
  }

  void pop() {
    assert(ssize(v) > 1);
    v.pop_back();
    pi.pop_back();
    int id = ranges::max_element(v.back()) - v.back().begin();
    v.back()[id] = v[pi.back()][id];
  }
};

Back to top page