C++ Library for Competitive Programming
#include "emthrm/string/morris-pratt.hpp"
文字列 $S$ に対して S[0:i]
の接頭辞と接尾辞の最大共通文字数 ($< i$) を求めるアルゴリズムである。
パターン長を $N$, テキスト長を $M$ とおく。
時間計算量 | |
---|---|
前処理 | $O(N)$ |
更新 | amortized $O(N)$ ? |
パターンマッチング | $O(M)$ |
struct MorrisPratt;
名前 | 説明 |
---|---|
std::string s |
文字列 $S$ |
std::vector<int> border |
$\mathrm{border}_i$ は S[0:i] の最長 border 長を表す。 |
名前 | 効果・戻り値 |
---|---|
explicit MorrisPratt(const std::string& s); |
文字列 $S$ に対してオブジェクトを構築する。 |
void add(const char c); |
$S$ の末尾に文字 $c$ を追加する。 |
std::vector<int> match(const std::string& t) const; |
$S$ が出現する文字列 $T$ 中の位置 |
int period(const int idx) const; |
S[0:idx] の最小周期 |
template <typename T = std::string>
struct KnuthMorrisPratt;
名前 | 説明 |
---|---|
std::vector<int> border |
border[i] は S[0:i] の最長 tagged border 長を表す。 |
名前 | 効果・戻り値 |
---|---|
explicit KnuthMorrisPratt(const T& s); |
文字列 $S$ に対してオブジェクトを構築する。 |
std::vector<int> match(const T& t) const; |
$S$ が出現する $T$ 中の位置 |
Morris–Pratt algorithm
Knuth–Morris–Pratt algorithm
周期性判定
パターンマッチング
#ifndef EMTHRM_STRING_MORRIS_PRATT_HPP_
#define EMTHRM_STRING_MORRIS_PRATT_HPP_
#include <string>
#include <vector>
namespace emthrm {
struct MorrisPratt {
std::string s;
std::vector<int> border;
explicit MorrisPratt(const std::string& s) : s(s), border({-1}), j(-1) {
const int n = s.length();
for (int i = 0; i < n; ++i) {
solve(i);
}
}
void add(const char c) {
s += c;
solve(s.length() - 1);
}
std::vector<int> match(const std::string& t) const {
const int n = s.length(), m = t.length();
std::vector<int> res;
for (int i = 0, k = 0; i < m; ++i) {
while (k >= 0 && t[i] != s[k]) k = border[k];
if (++k == n) res.emplace_back(i - n + 1);
}
return res;
}
int period(const int idx) const { return idx - border[idx]; }
private:
int j;
void solve(const int idx) {
while (j >= 0 && s[idx] != s[j]) j = border[j];
border.emplace_back(++j);
}
};
} // namespace emthrm
#endif // EMTHRM_STRING_MORRIS_PRATT_HPP_
#line 1 "include/emthrm/string/morris-pratt.hpp"
#include <string>
#include <vector>
namespace emthrm {
struct MorrisPratt {
std::string s;
std::vector<int> border;
explicit MorrisPratt(const std::string& s) : s(s), border({-1}), j(-1) {
const int n = s.length();
for (int i = 0; i < n; ++i) {
solve(i);
}
}
void add(const char c) {
s += c;
solve(s.length() - 1);
}
std::vector<int> match(const std::string& t) const {
const int n = s.length(), m = t.length();
std::vector<int> res;
for (int i = 0, k = 0; i < m; ++i) {
while (k >= 0 && t[i] != s[k]) k = border[k];
if (++k == n) res.emplace_back(i - n + 1);
}
return res;
}
int period(const int idx) const { return idx - border[idx]; }
private:
int j;
void solve(const int idx) {
while (j >= 0 && s[idx] != s[j]) j = border[j];
border.emplace_back(++j);
}
};
} // namespace emthrm