minimal_string.hpp¶
求序列的最小旋转及最早起点；适合项链规范化，字符串直接比较原生字符。
Complexity: Time: \(O(n)\), for constant-time coherent comparisons and copies. Space: \(O(1)\) auxiliary space, plus \(O(n)\) when returning a rotation.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n), for constant-time coherent comparisons and copies.
/// Space: O(1) auxiliary space, plus O(n) when returning a rotation.
#include <algorithm>
#include <string>
#include <vector>
namespace noya {
namespace minimal_string_internal {
template <class Seq> int index(const Seq &sec) {
int n = int(sec.size()), i = 0, j = 1, k = 0;
while (k < n && i < n && j < n) {
int a = i + k, b = j + k;
if (a >= n) a -= n;
if (b >= n) b -= n;
if (sec[a] == sec[b]) {
++k;
} else {
if (sec[a] > sec[b]) i += k + 1;
else j += k + 1;
if (i == j) ++i;
k = 0;
}
}
return std::min(i, j);
}
} // namespace minimal_string_internal
/// @brief Earliest starting index of a minimum rotation; empty input gives 0.
/// Symbols use coherent == and > comparisons; 2n must fit in int.
template <class T> int minimal_string_index(const std::vector<T> &sec) {
return minimal_string_internal::index(sec);
}
/// @brief Copy the minimum rotation; symbols need not be default-constructible.
template <class T> std::vector<T> minimal_string(const std::vector<T> &sec) {
int s = minimal_string_index(sec);
std::vector<T> ret;
ret.reserve(sec.size());
ret.insert(ret.end(), sec.begin() + s, sec.end());
ret.insert(ret.end(), sec.begin(), sec.begin() + s);
return ret;
}
/// @brief Minimum rotation under native plain-char order, without a symbol copy.
inline std::string minimal_string(const std::string &sec) {
int s = minimal_string_internal::index(sec);
std::string ret;
ret.reserve(sec.size());
ret.append(sec, s, sec.size() - s);
ret.append(sec, 0, s);
return ret;
}
} // namespace noya
// NOYA_MINIMAL_STRING_HPP
#ifndef NOYA_MINIMAL_STRING_HPP
#define NOYA_MINIMAL_STRING_HPP 1
/// @complexity Time: O(n), for constant-time coherent comparisons and copies.
/// Space: O(1) auxiliary space, plus O(n) when returning a rotation.
#include <algorithm>
#include <string>
#include <vector>
namespace noya {
namespace minimal_string_internal {
template <class Seq> int index(const Seq &sec) {
int n = int(sec.size()), i = 0, j = 1, k = 0;
while (k < n && i < n && j < n) {
int a = i + k, b = j + k;
if (a >= n) a -= n;
if (b >= n) b -= n;
if (sec[a] == sec[b]) {
++k;
} else {
if (sec[a] > sec[b]) i += k + 1;
else j += k + 1;
if (i == j) ++i;
k = 0;
}
}
return std::min(i, j);
}
} // namespace minimal_string_internal
/// @brief Earliest starting index of a minimum rotation; empty input gives 0.
/// Symbols use coherent == and > comparisons; 2n must fit in int.
template <class T> int minimal_string_index(const std::vector<T> &sec) {
return minimal_string_internal::index(sec);
}
/// @brief Copy the minimum rotation; symbols need not be default-constructible.
template <class T> std::vector<T> minimal_string(const std::vector<T> &sec) {
int s = minimal_string_index(sec);
std::vector<T> ret;
ret.reserve(sec.size());
ret.insert(ret.end(), sec.begin() + s, sec.end());
ret.insert(ret.end(), sec.begin(), sec.begin() + s);
return ret;
}
/// @brief Minimum rotation under native plain-char order, without a symbol copy.
inline std::string minimal_string(const std::string &sec) {
int s = minimal_string_internal::index(sec);
std::string ret;
ret.reserve(sec.size());
ret.append(sec, s, sec.size() - s);
ret.append(sec, 0, s);
return ret;
}
} // namespace noya
#endif // NOYA_MINIMAL_STRING_HPP
/// @complexity Time: O(n), for constant-time coherent comparisons and copies.
/// Space: O(1) auxiliary space, plus O(n) when returning a rotation.
#include <algorithm>
#include <string>
#include <vector>
namespace noya {
namespace minimal_string_internal {
template <class Seq> int index(const Seq &sec) {
int n = int(sec.size()), i = 0, j = 1, k = 0;
while (k < n && i < n && j < n) {
int a = i + k, b = j + k;
if (a >= n) a -= n;
if (b >= n) b -= n;
if (sec[a] == sec[b]) {
++k;
} else {
if (sec[a] > sec[b]) i += k + 1;
else j += k + 1;
if (i == j) ++i;
k = 0;
}
}
return std::min(i, j);
}
} // namespace minimal_string_internal
/// @brief Earliest starting index of a minimum rotation; empty input gives 0.
/// Symbols use coherent == and > comparisons; 2n must fit in int.
template <class T> int minimal_string_index(const std::vector<T> &sec) {
return minimal_string_internal::index(sec);
}
/// @brief Copy the minimum rotation; symbols need not be default-constructible.
template <class T> std::vector<T> minimal_string(const std::vector<T> &sec) {
int s = minimal_string_index(sec);
std::vector<T> ret;
ret.reserve(sec.size());
ret.insert(ret.end(), sec.begin() + s, sec.end());
ret.insert(ret.end(), sec.begin(), sec.begin() + s);
return ret;
}
/// @brief Minimum rotation under native plain-char order, without a symbol copy.
inline std::string minimal_string(const std::string &sec) {
int s = minimal_string_internal::index(sec);
std::string ret;
ret.reserve(sec.size());
ret.append(sec, s, sec.size() - s);
ret.append(sec, 0, s);
return ret;
}
} // namespace noya
// NOYA_MINIMAL_STRING_HPP