palindromic_automaton.hpp¶
构造回文树，在线记录字符串中所有不同回文子串及后缀回文关系。
Complexity: Time: \(O(n + m \cdot \mathrm{sig})\) for \(n\) appends and \(m\) nodes; \(m \le n + 2\). Space: \(O(n + m \cdot \mathrm{sig})\). A single append can traverse \(O(n)\) failure links.
AC 记录：eertree。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n + m * sig) for n appends and m nodes; m <= n + 2.
/// Space: O(n + m * sig). A single append can traverse O(n) failure links.
#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; // cnt counts longest-suffix visits, before propagation.
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.emplace_back(-1, 1, 0);
nd.emplace_back(-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 c in [0, sig); return the current longest-suffix node.
/// Nodes 0/1 are the even/odd roots; n+2 must fit in int. Existing ids stay stable.
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.emplace_back(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
// NOYA_PALINDROMIC_AUTOMATON_HPP
#ifndef NOYA_PALINDROMIC_AUTOMATON_HPP
#define NOYA_PALINDROMIC_AUTOMATON_HPP 1
/// @complexity Time: O(n + m * sig) for n appends and m nodes; m <= n + 2.
/// Space: O(n + m * sig). A single append can traverse O(n) failure links.
#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; // cnt counts longest-suffix visits, before propagation.
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.emplace_back(-1, 1, 0);
nd.emplace_back(-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 c in [0, sig); return the current longest-suffix node.
/// Nodes 0/1 are the even/odd roots; n+2 must fit in int. Existing ids stay stable.
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.emplace_back(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
/// @complexity Time: O(n + m * sig) for n appends and m nodes; m <= n + 2.
/// Space: O(n + m * sig). A single append can traverse O(n) failure links.
#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; // cnt counts longest-suffix visits, before propagation.
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.emplace_back(-1, 1, 0);
nd.emplace_back(-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 c in [0, sig); return the current longest-suffix node.
/// Nodes 0/1 are the even/odd roots; n+2 must fit in int. Existing ids stay stable.
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.emplace_back(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
// NOYA_PALINDROMIC_AUTOMATON_HPP