palindromic_automaton.hpp¶

SECTIONString INCLUDEnoya/palindromic_automaton.hpp

Palindromic automaton (Eertree) for enumerating distinct palindromic substrings.

Verified by eertree.

构造回文树，在线记录字符串中所有不同回文子串及后缀回文关系。

Implementation¶

SourceExpanded

#ifndef NOYA_PALINDROMIC_AUTOMATON_HPP
#define NOYA_PALINDROMIC_AUTOMATON_HPP 1

/// @complexity Time: O(n sigma) worst case with fixed-array transitions, O(n) for constant sigma.
/// Space: O(n sigma).

#include <algorithm>
#include <array>
#include <cassert>
#include <vector>

namespace noya {

/// @brief Palindromic automaton (Eertree) for enumerating distinct palindromic substrings.
template <int sigma = 26> struct palindromic_automaton {
  struct Node {
    std::array<int, sigma> next;
    int parent, fail, len, cnt;

    Node(int parent, int fail, int len)
        : parent(parent), fail(fail), len(len), cnt(0) {
      std::fill(next.begin(), next.end(), 0);
    }
  };

  std::vector<Node> nodes;
  std::vector<int> s;
  std::vector<int> suffix_node;
  int last = 0;

  palindromic_automaton() {
    nodes.push_back(Node(-1, 1, 0));
    nodes.push_back(Node(-1, 0, -1));
    s.push_back(-1);
    last = 0;
  }

  int get_fail(int x) {
    while (s[int(s.size()) - 1 - nodes[x].len - 1] != s.back()) {
      x = nodes[x].fail;
    }
    return x;
  }

  /// @brief Append character c (in [0, sigma)) and return the node id of the new longest palindromic suffix.
  int extend(int c) {
    assert(0 <= c && c < sigma);
    s.push_back(c);
    int cur = get_fail(last);
    if (!nodes[cur].next[c]) {
      int now = int(nodes.size());
      int fail = nodes[get_fail(nodes[cur].fail)].next[c];
      nodes.push_back(Node(cur, fail, nodes[cur].len + 2));
      nodes[cur].next[c] = now;
    }
    last = nodes[cur].next[c];
    nodes[last].cnt++;
    suffix_node.push_back(last);
    return last;
  }

  /// @brief Return the number of nodes in the automaton.
  int size() const { return int(nodes.size()); }
};

} // namespace noya

#endif // NOYA_PALINDROMIC_AUTOMATON_HPP

#include <algorithm>
#include <array>
#include <cassert>
#include <vector>

/// @complexity Time: O(n sigma) worst case with fixed-array transitions, O(n) for constant sigma.
/// Space: O(n sigma).

namespace noya {

/// @brief Palindromic automaton (Eertree) for enumerating distinct palindromic substrings.
template <int sigma = 26> struct palindromic_automaton {
  struct Node {
    std::array<int, sigma> next;
    int parent, fail, len, cnt;

    Node(int parent, int fail, int len)
        : parent(parent), fail(fail), len(len), cnt(0) {
      std::fill(next.begin(), next.end(), 0);
    }
  };

  std::vector<Node> nodes;
  std::vector<int> s;
  std::vector<int> suffix_node;
  int last = 0;

  palindromic_automaton() {
    nodes.push_back(Node(-1, 1, 0));
    nodes.push_back(Node(-1, 0, -1));
    s.push_back(-1);
    last = 0;
  }

  int get_fail(int x) {
    while (s[int(s.size()) - 1 - nodes[x].len - 1] != s.back()) {
      x = nodes[x].fail;
    }
    return x;
  }

  /// @brief Append character c (in [0, sigma)) and return the node id of the new longest palindromic suffix.
  int extend(int c) {
    assert(0 <= c && c < sigma);
    s.push_back(c);
    int cur = get_fail(last);
    if (!nodes[cur].next[c]) {
      int now = int(nodes.size());
      int fail = nodes[get_fail(nodes[cur].fail)].next[c];
      nodes.push_back(Node(cur, fail, nodes[cur].len + 2));
      nodes[cur].next[c] = now;
    }
    last = nodes[cur].next[c];
    nodes[last].cnt++;
    suffix_node.push_back(last);
    return last;
  }

  /// @brief Return the number of nodes in the automaton.
  int size() const { return int(nodes.size()); }
};

} // namespace noya