kmp.hpp¶

SECTIONString INCLUDEnoya/kmp.hpp

计算前缀函数并在线匹配单个模式串；适合查找出现位置、边界和字符串周期。

Complexity: Time: O(n + m). Space: O(n + m) including returned occurrences.

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n + m).
/// Space: O(n + m) including returned occurrences.

#include <numeric>
#include <string>
#include <vector>

namespace noya {

/// @brief Compute the prefix function of a sequence in O(n).
template <class T> std::vector<int> prefix_function(const std::vector<T> &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;
}

inline std::vector<int> prefix_function(const std::string &s) {
  return prefix_function(std::vector<char>(s.begin(), s.end()));
}

/// @brief Return all starting positions where pattern occurs in text.
template <class T>
std::vector<int> kmp_search(const std::vector<T> &src,
                            const std::vector<T> &t) {
  if (t.empty()) {
    std::vector<int> res(src.size() + 1);
    std::iota(res.begin(), res.end(), 0);
    return res;
  }
  std::vector<int> pre = 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;
}

inline std::vector<int> kmp_search(const std::string &src,
                                   const std::string &t) {
  return kmp_search(std::vector<char>(src.begin(), src.end()),
                    std::vector<char>(t.begin(), t.end()));
}

} // namespace noya

#ifndef NOYA_KMP_HPP
#define NOYA_KMP_HPP 1

/// @complexity Time: O(n + m).
/// Space: O(n + m) including returned occurrences.

#include <numeric>
#include <string>
#include <vector>

namespace noya {

/// @brief Compute the prefix function of a sequence in O(n).
template <class T> std::vector<int> prefix_function(const std::vector<T> &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;
}

inline std::vector<int> prefix_function(const std::string &s) {
  return prefix_function(std::vector<char>(s.begin(), s.end()));
}

/// @brief Return all starting positions where pattern occurs in text.
template <class T>
std::vector<int> kmp_search(const std::vector<T> &src,
                            const std::vector<T> &t) {
  if (t.empty()) {
    std::vector<int> res(src.size() + 1);
    std::iota(res.begin(), res.end(), 0);
    return res;
  }
  std::vector<int> pre = 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;
}

inline std::vector<int> kmp_search(const std::string &src,
                                   const std::string &t) {
  return kmp_search(std::vector<char>(src.begin(), src.end()),
                    std::vector<char>(t.begin(), t.end()));
}

} // namespace noya

#endif // NOYA_KMP_HPP

#include <numeric>
#include <string>
#include <vector>

/// @complexity Time: O(n + m).
/// Space: O(n + m) including returned occurrences.

namespace noya {

/// @brief Compute the prefix function of a sequence in O(n).
template <class T> std::vector<int> prefix_function(const std::vector<T> &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;
}

inline std::vector<int> prefix_function(const std::string &s) {
  return prefix_function(std::vector<char>(s.begin(), s.end()));
}

/// @brief Return all starting positions where pattern occurs in text.
template <class T>
std::vector<int> kmp_search(const std::vector<T> &src,
                            const std::vector<T> &t) {
  if (t.empty()) {
    std::vector<int> res(src.size() + 1);
    std::iota(res.begin(), res.end(), 0);
    return res;
  }
  std::vector<int> pre = 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;
}

inline std::vector<int> kmp_search(const std::string &src,
                                   const std::string &t) {
  return kmp_search(std::vector<char>(src.begin(), src.end()),
                    std::vector<char>(t.begin(), t.end()));
}

} // namespace noya