lyndon_factor.hpp¶
用 Duval 算法把序列唯一分解为字典序非增的 Lyndon 串，返回含 0 和 \(n\) 的边界；字符串直接遍历，空输入返回单个 0。
Complexity: Time: \(O(n)\), for constant-time coherent comparisons. Space: \(O(f + 1)\) returned boundaries and \(O(1)\) auxiliary space, for \(f\) factors.
AC 记录：lyndon_factorization。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n), for constant-time coherent comparisons.
/// Space: O(f + 1) returned boundaries and O(1) auxiliary space, for f factors.
#include <string>
#include <vector>
namespace noya {
namespace lyndon_internal {
template <class Seq> std::vector<int> factor(const Seq &s) {
int n = int(s.size());
std::vector<int> res{0};
for (int i = 0; i < n;) {
int j = i + 1, k = i;
for (; j < n && s[k] <= s[j]; j += 1)
k = s[k] < s[j] ? i : k + 1;
while (i <= k)
res.push_back(i += j - k);
}
return res;
}
} // namespace lyndon_internal
/// @brief Nonincreasing Lyndon factorization as boundaries including 0 and n.
/// Empty input returns {0}. Symbols use their coherent < and <= ordering.
template <class T> std::vector<int> lyndon(const std::vector<T> &s) {
return lyndon_internal::factor(s);
}
/// @brief Traverse characters directly, retaining native plain-char ordering.
inline std::vector<int> lyndon(const std::string &s) {
return lyndon_internal::factor(s);
}
} // namespace noya
// NOYA_LYNDON_FACTOR_HPP
#ifndef NOYA_LYNDON_FACTOR_HPP
#define NOYA_LYNDON_FACTOR_HPP 1
/// @complexity Time: O(n), for constant-time coherent comparisons.
/// Space: O(f + 1) returned boundaries and O(1) auxiliary space, for f factors.
#include <string>
#include <vector>
namespace noya {
namespace lyndon_internal {
template <class Seq> std::vector<int> factor(const Seq &s) {
int n = int(s.size());
std::vector<int> res{0};
for (int i = 0; i < n;) {
int j = i + 1, k = i;
for (; j < n && s[k] <= s[j]; j += 1)
k = s[k] < s[j] ? i : k + 1;
while (i <= k)
res.push_back(i += j - k);
}
return res;
}
} // namespace lyndon_internal
/// @brief Nonincreasing Lyndon factorization as boundaries including 0 and n.
/// Empty input returns {0}. Symbols use their coherent < and <= ordering.
template <class T> std::vector<int> lyndon(const std::vector<T> &s) {
return lyndon_internal::factor(s);
}
/// @brief Traverse characters directly, retaining native plain-char ordering.
inline std::vector<int> lyndon(const std::string &s) {
return lyndon_internal::factor(s);
}
} // namespace noya
#endif // NOYA_LYNDON_FACTOR_HPP
/// @complexity Time: O(n), for constant-time coherent comparisons.
/// Space: O(f + 1) returned boundaries and O(1) auxiliary space, for f factors.
#include <string>
#include <vector>
namespace noya {
namespace lyndon_internal {
template <class Seq> std::vector<int> factor(const Seq &s) {
int n = int(s.size());
std::vector<int> res{0};
for (int i = 0; i < n;) {
int j = i + 1, k = i;
for (; j < n && s[k] <= s[j]; j += 1)
k = s[k] < s[j] ? i : k + 1;
while (i <= k)
res.push_back(i += j - k);
}
return res;
}
} // namespace lyndon_internal
/// @brief Nonincreasing Lyndon factorization as boundaries including 0 and n.
/// Empty input returns {0}. Symbols use their coherent < and <= ordering.
template <class T> std::vector<int> lyndon(const std::vector<T> &s) {
return lyndon_internal::factor(s);
}
/// @brief Traverse characters directly, retaining native plain-char ordering.
inline std::vector<int> lyndon(const std::string &s) {
return lyndon_internal::factor(s);
}
} // namespace noya
// NOYA_LYNDON_FACTOR_HPP