C++ Library for Competitive Programming
#include "emthrm/string/z_algorithm.hpp"
文字列 $S$ に対して $S$ と S[i:]
の最長共通接頭辞の長さを求めるアルゴリズムである。
$O(\lvert S \rvert)$
名前 | 戻り値 |
---|---|
template <typename T> std::vector<int> z_algorithm(const T &s);
|
$S$ と S[i:] の最長共通接頭辞の長さ |
https://judge.yosupo.jp/submission/27816
#ifndef EMTHRM_STRING_Z_ALGORITHM_HPP_
#define EMTHRM_STRING_Z_ALGORITHM_HPP_
#include <algorithm>
#include <vector>
namespace emthrm {
template <typename T>
std::vector<int> z_algorithm(const T &s) {
const int n = s.size();
std::vector<int> res(n, 0);
for (int i = 1, j = 0; i < n; ++i) {
if (i + res[i - j] < j + res[j]) {
res[i] = res[i - j];
} else {
res[i] = std::max(j + res[j] - i, 0);
while (i + res[i] < n && s[i + res[i]] == s[res[i]]) ++res[i];
j = i;
}
}
res[0] = n;
return res;
}
} // namespace emthrm
#endif // EMTHRM_STRING_Z_ALGORITHM_HPP_
#line 1 "include/emthrm/string/z_algorithm.hpp"
#include <algorithm>
#include <vector>
namespace emthrm {
template <typename T>
std::vector<int> z_algorithm(const T &s) {
const int n = s.size();
std::vector<int> res(n, 0);
for (int i = 1, j = 0; i < n; ++i) {
if (i + res[i - j] < j + res[j]) {
res[i] = res[i - j];
} else {
res[i] = std::max(j + res[j] - i, 0);
while (i + res[i] < n && s[i + res[i]] == s[res[i]]) ++res[i];
j = i;
}
}
res[0] = n;
return res;
}
} // namespace emthrm