kmp.hpp¶
计算最长真 border 的前缀函数或查找单个模式的全部重叠位置；字符串直接遍历，空模式匹配全部边界，模式更长时直接返回空结果。
Complexity: Time: prefix \(O(n)\), search \(O(n + m)\), for constant-time equality. Space: prefix \(O(n)\), search \(O(m + z)\), including \(z\) returned occurrences.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: prefix O(n), search O(n + m), for constant-time equality.
/// Space: prefix O(n), search O(m + z), including z returned occurrences.
#include <numeric>
#include <string>
#include <vector>
namespace noya {
namespace kmp_internal {
template <class Seq> std::vector<int> prefix_function(const Seq &s) {
std::vector<int> pre(s.size());
for (int i = 1; i < int(s.size()); i++) {
int bd = pre[i - 1];
while (bd > 0 && s[i] != s[bd]) bd = pre[bd - 1];
if (s[i] == s[bd]) bd++;
pre[i] = bd;
}
return pre;
}
template <class Seq>
std::vector<int> search(const Seq &src, const Seq &t) {
if (t.size() > src.size()) return {};
if (t.empty()) {
std::vector<int> res(src.size() + 1);
std::iota(res.begin(), res.end(), 0);
return res;
}
std::vector<int> pre = kmp_internal::prefix_function(t);
std::vector<int> res;
int mat = 0;
for (int i = 0; i < int(src.size()); i++) {
while (mat > 0 && src[i] != t[mat]) mat = pre[mat - 1];
if (src[i] == t[mat]) mat++;
if (mat == int(t.size())) {
res.push_back(i + 1 - mat);
mat = pre[mat - 1];
}
}
return res;
}
} // namespace kmp_internal
/// @brief Longest proper prefix/suffix length at each sequence position.
template <class T> std::vector<int> prefix_function(const std::vector<T> &s) {
return kmp_internal::prefix_function(s);
}
inline std::vector<int> prefix_function(const std::string &s) {
return kmp_internal::prefix_function(s);
}
/// @brief All match starts in ascending order, including overlaps.
/// An empty pattern matches all text boundaries 0..text.size().
template <class T>
std::vector<int> kmp_search(const std::vector<T> &src, const std::vector<T> &t) {
return kmp_internal::search(src, t);
}
inline std::vector<int> kmp_search(const std::string &src, const std::string &t) {
return kmp_internal::search(src, t);
}
} // namespace noya
// NOYA_KMP_HPP
#ifndef NOYA_KMP_HPP
#define NOYA_KMP_HPP 1
/// @complexity Time: prefix O(n), search O(n + m), for constant-time equality.
/// Space: prefix O(n), search O(m + z), including z returned occurrences.
#include <numeric>
#include <string>
#include <vector>
namespace noya {
namespace kmp_internal {
template <class Seq> std::vector<int> prefix_function(const Seq &s) {
std::vector<int> pre(s.size());
for (int i = 1; i < int(s.size()); i++) {
int bd = pre[i - 1];
while (bd > 0 && s[i] != s[bd]) bd = pre[bd - 1];
if (s[i] == s[bd]) bd++;
pre[i] = bd;
}
return pre;
}
template <class Seq>
std::vector<int> search(const Seq &src, const Seq &t) {
if (t.size() > src.size()) return {};
if (t.empty()) {
std::vector<int> res(src.size() + 1);
std::iota(res.begin(), res.end(), 0);
return res;
}
std::vector<int> pre = kmp_internal::prefix_function(t);
std::vector<int> res;
int mat = 0;
for (int i = 0; i < int(src.size()); i++) {
while (mat > 0 && src[i] != t[mat]) mat = pre[mat - 1];
if (src[i] == t[mat]) mat++;
if (mat == int(t.size())) {
res.push_back(i + 1 - mat);
mat = pre[mat - 1];
}
}
return res;
}
} // namespace kmp_internal
/// @brief Longest proper prefix/suffix length at each sequence position.
template <class T> std::vector<int> prefix_function(const std::vector<T> &s) {
return kmp_internal::prefix_function(s);
}
inline std::vector<int> prefix_function(const std::string &s) {
return kmp_internal::prefix_function(s);
}
/// @brief All match starts in ascending order, including overlaps.
/// An empty pattern matches all text boundaries 0..text.size().
template <class T>
std::vector<int> kmp_search(const std::vector<T> &src, const std::vector<T> &t) {
return kmp_internal::search(src, t);
}
inline std::vector<int> kmp_search(const std::string &src, const std::string &t) {
return kmp_internal::search(src, t);
}
} // namespace noya
#endif // NOYA_KMP_HPP
/// @complexity Time: prefix O(n), search O(n + m), for constant-time equality.
/// Space: prefix O(n), search O(m + z), including z returned occurrences.
#include <numeric>
#include <string>
#include <vector>
namespace noya {
namespace kmp_internal {
template <class Seq> std::vector<int> prefix_function(const Seq &s) {
std::vector<int> pre(s.size());
for (int i = 1; i < int(s.size()); i++) {
int bd = pre[i - 1];
while (bd > 0 && s[i] != s[bd]) bd = pre[bd - 1];
if (s[i] == s[bd]) bd++;
pre[i] = bd;
}
return pre;
}
template <class Seq>
std::vector<int> search(const Seq &src, const Seq &t) {
if (t.size() > src.size()) return {};
if (t.empty()) {
std::vector<int> res(src.size() + 1);
std::iota(res.begin(), res.end(), 0);
return res;
}
std::vector<int> pre = kmp_internal::prefix_function(t);
std::vector<int> res;
int mat = 0;
for (int i = 0; i < int(src.size()); i++) {
while (mat > 0 && src[i] != t[mat]) mat = pre[mat - 1];
if (src[i] == t[mat]) mat++;
if (mat == int(t.size())) {
res.push_back(i + 1 - mat);
mat = pre[mat - 1];
}
}
return res;
}
} // namespace kmp_internal
/// @brief Longest proper prefix/suffix length at each sequence position.
template <class T> std::vector<int> prefix_function(const std::vector<T> &s) {
return kmp_internal::prefix_function(s);
}
inline std::vector<int> prefix_function(const std::string &s) {
return kmp_internal::prefix_function(s);
}
/// @brief All match starts in ascending order, including overlaps.
/// An empty pattern matches all text boundaries 0..text.size().
template <class T>
std::vector<int> kmp_search(const std::vector<T> &src, const std::vector<T> &t) {
return kmp_internal::search(src, t);
}
inline std::vector<int> kmp_search(const std::string &src, const std::string &t) {
return kmp_internal::search(src, t);
}
} // namespace noya
// NOYA_KMP_HPP