kmp.hpp¶

SECTIONString INCLUDEnoya/kmp.hpp

Compute the prefix function of a sequence in O(n).

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

Implementation¶

SourceExpanded

#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> prefix(s.size());
  for (int i = 1; i < int(s.size()); i++) {
    int border = prefix[i - 1];
    while (border > 0 && s[i] != s[border]) {
      border = prefix[border - 1];
    }
    if (s[i] == s[border]) {
      border++;
    }
    prefix[i] = border;
  }
  return prefix;
}

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> &text,
                            const std::vector<T> &pattern) {
  if (pattern.empty()) {
    std::vector<int> result(text.size() + 1);
    std::iota(result.begin(), result.end(), 0);
    return result;
  }
  std::vector<int> prefix = prefix_function(pattern);
  std::vector<int> result;
  int matched = 0;
  for (int i = 0; i < int(text.size()); i++) {
    while (matched > 0 && text[i] != pattern[matched]) {
      matched = prefix[matched - 1];
    }
    if (text[i] == pattern[matched]) {
      matched++;
    }
    if (matched == int(pattern.size())) {
      result.push_back(i + 1 - matched);
      matched = prefix[matched - 1];
    }
  }
  return result;
}

inline std::vector<int> kmp_search(const std::string &text,
                                   const std::string &pattern) {
  return kmp_search(std::vector<char>(text.begin(), text.end()),
                    std::vector<char>(pattern.begin(), pattern.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> prefix(s.size());
  for (int i = 1; i < int(s.size()); i++) {
    int border = prefix[i - 1];
    while (border > 0 && s[i] != s[border]) {
      border = prefix[border - 1];
    }
    if (s[i] == s[border]) {
      border++;
    }
    prefix[i] = border;
  }
  return prefix;
}

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> &text,
                            const std::vector<T> &pattern) {
  if (pattern.empty()) {
    std::vector<int> result(text.size() + 1);
    std::iota(result.begin(), result.end(), 0);
    return result;
  }
  std::vector<int> prefix = prefix_function(pattern);
  std::vector<int> result;
  int matched = 0;
  for (int i = 0; i < int(text.size()); i++) {
    while (matched > 0 && text[i] != pattern[matched]) {
      matched = prefix[matched - 1];
    }
    if (text[i] == pattern[matched]) {
      matched++;
    }
    if (matched == int(pattern.size())) {
      result.push_back(i + 1 - matched);
      matched = prefix[matched - 1];
    }
  }
  return result;
}

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

} // namespace noya