Z algorithm
(include/emthrm/string/z_algorithm.hpp)

• View this file on GitHub
• Last update: 2022-12-15 22:18:37+09:00
• Include: #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:] の最長共通接頭辞の長さ

参考文献

• Dan Gusfield: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, pp. 9–10 (1997). https://doi.org/10.1017/CBO9780511574931
• https://snuke.hatenablog.com/entry/2014/12/03/214243
• https://sen-comp.hatenablog.com/entry/2020/01/16/174230

TODO

• 動的 Z algorithm
  • https://heno239.hatenablog.com/entry/2020/07/07/140651

Submissons

https://judge.yosupo.jp/submission/27816

Verified with

• 文字列/Z algorithm (test/string/z_algorithm.test.cpp)

Code

#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

Back to top page