palindromic_automaton.hpp¶

SECTIONString INCLUDEnoya/palindromic_automaton.hpp

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

Complexity: Time: O(n sig) worst case with fixed-array transitions, O(n) for constant sig. Space: O(n sig).

AC 记录：eertree。

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

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

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

namespace noya {

/// @brief Palindromic automaton (Eertree) for enumerating distinct palindromic substrings.
template <int sig = 26> struct palindromic_automaton {
  struct Node {
    std::array<int, sig> nxt;
    int fa, fal, len, cnt;

    Node(int fa, int fal, int len)
        : fa(fa), fal(fal), len(len), cnt(0) {
      std::fill(nxt.begin(), nxt.end(), 0);
    }
  };

  std::vector<Node> nd;
  std::vector<int> s;
  std::vector<int> sn;
  int lst = 0;

  palindromic_automaton() {
    nd.push_back(Node(-1, 1, 0));
    nd.push_back(Node(-1, 0, -1));
    s.push_back(-1);
    lst = 0;
  }

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

  /// @brief Append character c (in [0, sig)) and return the node id of the new longest palindromic suffix.
  int extend(int c) {
    assert(0 <= c && c < sig);
    s.push_back(c);
    int cur = get_fail(lst);
    if (!nd[cur].nxt[c]) {
      int now = int(nd.size());
      int fal = nd[get_fail(nd[cur].fal)].nxt[c];
      nd.push_back(Node(cur, fal, nd[cur].len + 2));
      nd[cur].nxt[c] = now;
    }
    lst = nd[cur].nxt[c];
    nd[lst].cnt++;
    sn.push_back(lst);
    return lst;
  }

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

} // namespace noya

#ifndef NOYA_PALINDROMIC_AUTOMATON_HPP
#define NOYA_PALINDROMIC_AUTOMATON_HPP 1

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

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

namespace noya {

/// @brief Palindromic automaton (Eertree) for enumerating distinct palindromic substrings.
template <int sig = 26> struct palindromic_automaton {
  struct Node {
    std::array<int, sig> nxt;
    int fa, fal, len, cnt;

    Node(int fa, int fal, int len)
        : fa(fa), fal(fal), len(len), cnt(0) {
      std::fill(nxt.begin(), nxt.end(), 0);
    }
  };

  std::vector<Node> nd;
  std::vector<int> s;
  std::vector<int> sn;
  int lst = 0;

  palindromic_automaton() {
    nd.push_back(Node(-1, 1, 0));
    nd.push_back(Node(-1, 0, -1));
    s.push_back(-1);
    lst = 0;
  }

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

  /// @brief Append character c (in [0, sig)) and return the node id of the new longest palindromic suffix.
  int extend(int c) {
    assert(0 <= c && c < sig);
    s.push_back(c);
    int cur = get_fail(lst);
    if (!nd[cur].nxt[c]) {
      int now = int(nd.size());
      int fal = nd[get_fail(nd[cur].fal)].nxt[c];
      nd.push_back(Node(cur, fal, nd[cur].len + 2));
      nd[cur].nxt[c] = now;
    }
    lst = nd[cur].nxt[c];
    nd[lst].cnt++;
    sn.push_back(lst);
    return lst;
  }

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

} // namespace noya

#endif // NOYA_PALINDROMIC_AUTOMATON_HPP

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

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

namespace noya {

/// @brief Palindromic automaton (Eertree) for enumerating distinct palindromic substrings.
template <int sig = 26> struct palindromic_automaton {
  struct Node {
    std::array<int, sig> nxt;
    int fa, fal, len, cnt;

    Node(int fa, int fal, int len)
        : fa(fa), fal(fal), len(len), cnt(0) {
      std::fill(nxt.begin(), nxt.end(), 0);
    }
  };

  std::vector<Node> nd;
  std::vector<int> s;
  std::vector<int> sn;
  int lst = 0;

  palindromic_automaton() {
    nd.push_back(Node(-1, 1, 0));
    nd.push_back(Node(-1, 0, -1));
    s.push_back(-1);
    lst = 0;
  }

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

  /// @brief Append character c (in [0, sig)) and return the node id of the new longest palindromic suffix.
  int extend(int c) {
    assert(0 <= c && c < sig);
    s.push_back(c);
    int cur = get_fail(lst);
    if (!nd[cur].nxt[c]) {
      int now = int(nd.size());
      int fal = nd[get_fail(nd[cur].fal)].nxt[c];
      nd.push_back(Node(cur, fal, nd[cur].len + 2));
      nd[cur].nxt[c] = now;
    }
    lst = nd[cur].nxt[c];
    nd[lst].cnt++;
    sn.push_back(lst);
    return lst;
  }

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

} // namespace noya