suffix_automaton.hpp¶
构造后缀自动机表示所有子串；用于子串存在性、不同子串计数、出现次数和最长匹配。
Complexity: Time: O(n sig) storage and O(n) construction for constant alphabet sig. Space: O(n sig).
AC 记录：number_of_substrings。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n sig) storage and O(n) construction for constant alphabet sig.
/// Space: O(n sig).
#include <algorithm>
#include <array>
#include <cassert>
#include <map>
#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.
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.push_back(Node(-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.push_back(Node(-1, nd[lst].len + 1));
int p = lst;
while (p != -1 && nd[p].nxt[c] == -1) {
nd[p].nxt[c] = nn;
p = nd[p].lnk;
}
int q = (p == -1 ? 0 : nd[p].nxt[c]);
if (p == -1 || nd[p].len + 1 == nd[q].len) {
nd[nn].lnk = q;
} else {
int nq = int(nd.size());
nd.push_back(Node(nd[q].lnk, nd[p].len + 1));
nd.back().nxt = nd[q].nxt;
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 as an adjacency list.
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 node i.
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
#ifndef NOYA_SUFFIX_AUTOMATON_HPP
#define NOYA_SUFFIX_AUTOMATON_HPP 1
/// @complexity Time: O(n sig) storage and O(n) construction for constant alphabet sig.
/// Space: O(n sig).
#include <algorithm>
#include <array>
#include <cassert>
#include <map>
#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.
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.push_back(Node(-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.push_back(Node(-1, nd[lst].len + 1));
int p = lst;
while (p != -1 && nd[p].nxt[c] == -1) {
nd[p].nxt[c] = nn;
p = nd[p].lnk;
}
int q = (p == -1 ? 0 : nd[p].nxt[c]);
if (p == -1 || nd[p].len + 1 == nd[q].len) {
nd[nn].lnk = q;
} else {
int nq = int(nd.size());
nd.push_back(Node(nd[q].lnk, nd[p].len + 1));
nd.back().nxt = nd[q].nxt;
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 as an adjacency list.
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 node i.
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
#include <algorithm>
#include <array>
#include <cassert>
#include <map>
#include <vector>
/// @complexity Time: O(n sig) storage and O(n) construction for constant alphabet sig.
/// Space: O(n sig).
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.
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.push_back(Node(-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.push_back(Node(-1, nd[lst].len + 1));
int p = lst;
while (p != -1 && nd[p].nxt[c] == -1) {
nd[p].nxt[c] = nn;
p = nd[p].lnk;
}
int q = (p == -1 ? 0 : nd[p].nxt[c]);
if (p == -1 || nd[p].len + 1 == nd[q].len) {
nd[nn].lnk = q;
} else {
int nq = int(nd.size());
nd.push_back(Node(nd[q].lnk, nd[p].len + 1));
nd.back().nxt = nd[q].nxt;
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 as an adjacency list.
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 node i.
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