suffix_automaton.hpp¶
构造后缀自动机表示所有子串；用于子串存在性、不同子串计数、出现次数和最长匹配。
Complexity: Time: \(O(n \mathrm{sig})\) construction; \(O(m)\) total count / suffix-link tree. Space: \(O(m \mathrm{sig})\) automaton, \(O(m)\) returned tree; \(m \le 2 n + 1\) states.
Source: maspy
AC 记录：number_of_substrings。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n sig) construction; O(m) total count / suffix-link tree.
/// Space: O(m sig) automaton, O(m) returned tree; m <= 2n+1 states.
#include <algorithm>
#include <array>
#include <cassert>
#include <vector>
namespace noya {
/// @brief Suffix automaton (SAM) for online suffix structure construction.
/// Each state represents substrings sharing an end-position set. Extending by
/// one character redirects missing transitions along suffix links; when the
/// target has excessive length, a clone splits its end-position class while
/// preserving transitions, keeping at most two new states per character.
/// Encode symbols in [0,sig); all lengths and state ids must fit in int.
/// A single extend can be linear; construction is amortized over all appends.
template <int sig = 26> struct suffix_automaton {
struct Node {
std::array<int, sig> nxt;
int lnk;
int len;
Node(int lnk, int len) : lnk(lnk), len(len) {
std::fill(nxt.begin(), nxt.end(), -1);
}
};
std::vector<Node> nd;
int lst = 0;
suffix_automaton() {
nd.emplace_back(-1, 0);
lst = 0;
}
/// @brief Append character c (in [0, sig)) and return the new node id.
int extend(int c) {
assert(0 <= c && c < sig);
int nn = int(nd.size());
nd.emplace_back(-1, nd[lst].len + 1);
int p = lst, q = 0;
while (p != -1 && (q = nd[p].nxt[c]) == -1) {
nd[p].nxt[c] = nn;
p = nd[p].lnk;
}
if (p == -1) q = 0;
if (p == -1 || nd[p].len + 1 == nd[q].len) {
nd[nn].lnk = q;
} else {
int nq = int(nd.size());
nd.push_back(nd[q]); // Copy the clone once, without filling unused slots first.
nd.back().len = nd[p].len + 1;
nd[q].lnk = nq;
nd[nn].lnk = nq;
while (p != -1 && nd[p].nxt[c] == q) {
nd[p].nxt[c] = nq;
p = nd[p].lnk;
}
}
return lst = nn;
}
/// @brief Return the suffix-link tree, with child ids in increasing order.
std::vector<std::vector<int>> get_tree() const {
int n = int(nd.size());
std::vector<std::vector<int>> g(n);
for (int i = 1; i < n; i++) {
g[nd[i].lnk].push_back(i);
}
return g;
}
/// @brief Return the number of distinct substrings represented by valid node i, O(1).
/// This counts lengths in its end-position class, not occurrences in the text.
long long count_substring_at(int i) const {
if (i == 0) {
return 0;
} else {
return nd[i].len - nd[nd[i].lnk].len;
}
};
/// @brief Return the total number of distinct non-empty substrings.
long long count_substring() const {
long long ans = 0;
int n = int(nd.size());
for (int i = 1; i < n; i++) {
ans += count_substring_at(i);
}
return ans;
}
};
} // namespace noya
// NOYA_SUFFIX_AUTOMATON_HPP
#ifndef NOYA_SUFFIX_AUTOMATON_HPP
#define NOYA_SUFFIX_AUTOMATON_HPP 1
/// @complexity Time: O(n sig) construction; O(m) total count / suffix-link tree.
/// Space: O(m sig) automaton, O(m) returned tree; m <= 2n+1 states.
#include <algorithm>
#include <array>
#include <cassert>
#include <vector>
namespace noya {
/// @brief Suffix automaton (SAM) for online suffix structure construction.
/// Each state represents substrings sharing an end-position set. Extending by
/// one character redirects missing transitions along suffix links; when the
/// target has excessive length, a clone splits its end-position class while
/// preserving transitions, keeping at most two new states per character.
/// Encode symbols in [0,sig); all lengths and state ids must fit in int.
/// A single extend can be linear; construction is amortized over all appends.
template <int sig = 26> struct suffix_automaton {
struct Node {
std::array<int, sig> nxt;
int lnk;
int len;
Node(int lnk, int len) : lnk(lnk), len(len) {
std::fill(nxt.begin(), nxt.end(), -1);
}
};
std::vector<Node> nd;
int lst = 0;
suffix_automaton() {
nd.emplace_back(-1, 0);
lst = 0;
}
/// @brief Append character c (in [0, sig)) and return the new node id.
int extend(int c) {
assert(0 <= c && c < sig);
int nn = int(nd.size());
nd.emplace_back(-1, nd[lst].len + 1);
int p = lst, q = 0;
while (p != -1 && (q = nd[p].nxt[c]) == -1) {
nd[p].nxt[c] = nn;
p = nd[p].lnk;
}
if (p == -1) q = 0;
if (p == -1 || nd[p].len + 1 == nd[q].len) {
nd[nn].lnk = q;
} else {
int nq = int(nd.size());
nd.push_back(nd[q]); // Copy the clone once, without filling unused slots first.
nd.back().len = nd[p].len + 1;
nd[q].lnk = nq;
nd[nn].lnk = nq;
while (p != -1 && nd[p].nxt[c] == q) {
nd[p].nxt[c] = nq;
p = nd[p].lnk;
}
}
return lst = nn;
}
/// @brief Return the suffix-link tree, with child ids in increasing order.
std::vector<std::vector<int>> get_tree() const {
int n = int(nd.size());
std::vector<std::vector<int>> g(n);
for (int i = 1; i < n; i++) {
g[nd[i].lnk].push_back(i);
}
return g;
}
/// @brief Return the number of distinct substrings represented by valid node i, O(1).
/// This counts lengths in its end-position class, not occurrences in the text.
long long count_substring_at(int i) const {
if (i == 0) {
return 0;
} else {
return nd[i].len - nd[nd[i].lnk].len;
}
};
/// @brief Return the total number of distinct non-empty substrings.
long long count_substring() const {
long long ans = 0;
int n = int(nd.size());
for (int i = 1; i < n; i++) {
ans += count_substring_at(i);
}
return ans;
}
};
} // namespace noya
#endif // NOYA_SUFFIX_AUTOMATON_HPP
/// @complexity Time: O(n sig) construction; O(m) total count / suffix-link tree.
/// Space: O(m sig) automaton, O(m) returned tree; m <= 2n+1 states.
#include <algorithm>
#include <array>
#include <cassert>
#include <vector>
namespace noya {
/// @brief Suffix automaton (SAM) for online suffix structure construction.
/// Each state represents substrings sharing an end-position set. Extending by
/// one character redirects missing transitions along suffix links; when the
/// target has excessive length, a clone splits its end-position class while
/// preserving transitions, keeping at most two new states per character.
/// Encode symbols in [0,sig); all lengths and state ids must fit in int.
/// A single extend can be linear; construction is amortized over all appends.
template <int sig = 26> struct suffix_automaton {
struct Node {
std::array<int, sig> nxt;
int lnk;
int len;
Node(int lnk, int len) : lnk(lnk), len(len) {
std::fill(nxt.begin(), nxt.end(), -1);
}
};
std::vector<Node> nd;
int lst = 0;
suffix_automaton() {
nd.emplace_back(-1, 0);
lst = 0;
}
/// @brief Append character c (in [0, sig)) and return the new node id.
int extend(int c) {
assert(0 <= c && c < sig);
int nn = int(nd.size());
nd.emplace_back(-1, nd[lst].len + 1);
int p = lst, q = 0;
while (p != -1 && (q = nd[p].nxt[c]) == -1) {
nd[p].nxt[c] = nn;
p = nd[p].lnk;
}
if (p == -1) q = 0;
if (p == -1 || nd[p].len + 1 == nd[q].len) {
nd[nn].lnk = q;
} else {
int nq = int(nd.size());
nd.push_back(nd[q]); // Copy the clone once, without filling unused slots first.
nd.back().len = nd[p].len + 1;
nd[q].lnk = nq;
nd[nn].lnk = nq;
while (p != -1 && nd[p].nxt[c] == q) {
nd[p].nxt[c] = nq;
p = nd[p].lnk;
}
}
return lst = nn;
}
/// @brief Return the suffix-link tree, with child ids in increasing order.
std::vector<std::vector<int>> get_tree() const {
int n = int(nd.size());
std::vector<std::vector<int>> g(n);
for (int i = 1; i < n; i++) {
g[nd[i].lnk].push_back(i);
}
return g;
}
/// @brief Return the number of distinct substrings represented by valid node i, O(1).
/// This counts lengths in its end-position class, not occurrences in the text.
long long count_substring_at(int i) const {
if (i == 0) {
return 0;
} else {
return nd[i].len - nd[nd[i].lnk].len;
}
};
/// @brief Return the total number of distinct non-empty substrings.
long long count_substring() const {
long long ans = 0;
int n = int(nd.size());
for (int i = 1; i < n; i++) {
ans += count_substring_at(i);
}
return ans;
}
};
} // namespace noya
// NOYA_SUFFIX_AUTOMATON_HPP