Z algorithm
(include/string/z_algorithm.hpp)

• View this file on GitHub
• Last update: 2021-08-11 13:32:54+09:00
• Include: #include "include/string/z_algorithm.hpp"

Z algorithm を用いて最長共通接頭辞の長さを格納した配列を求める関数が定義されています。

---

z_algorithm(S)

S 内の各位置についての最長共通接頭辞の長さを格納した配列を返します。S として文字列だけではなく std::vector<int> 等のコンテナを渡すこともできます。

例えば std::string 型の値 S が "abcabcabc" の時、z_algorithm(S) の値は std::vector<int> 型の値 { 9 0 0 6 0 0 3 0 0 } となります。

---

Verified with

• test/string/z_algorithm/1.test.cpp

Code

//! @file z_algorithm.hpp
//! @details Provide a function to calculate the length of the longest common prefix.

#ifndef CP_LIBRARY_Z_ALGORITHM_HPP
#define CP_LIBRARY_Z_ALGORITHM_HPP

#include <iterator>
#include <vector>

namespace lib {

//! @tparam Container container type (deduced from parameter). operator[] and size(Container) must be defined.
//! @param src Source (container)
//! @return Vector contains the length of the longest common prefix
//! @note Time complexity: O(size(s))
template <typename Container>
[[nodiscard]] std::vector<int> z_algorithm(const Container& src) {
  const int size = static_cast<int>(std::size(src));

  std::vector<int> res(size);
  res[0] = size;

  for (int i = 1, l = 0, r = 0; i < size; ++i) {
    if (i <= r) {
      res[i] = std::min(r - i + 1, res[i - l]);
    }
    while (i + res[i] < size && src[i + res[i]] == src[res[i]]) {
      ++res[i];
    }
    if (i + res[i] - 1 > r) {
      l = i;
      r = i + res[i] - 1;
    }
  }

  return res;
}

}  // namespace lib

#endif  // CP_LIBRARY_Z_ALGORITHM_HPP

#line 1 "include/string/z_algorithm.hpp"

//! @file z_algorithm.hpp
//! @details Provide a function to calculate the length of the longest common prefix.

#ifndef CP_LIBRARY_Z_ALGORITHM_HPP
#define CP_LIBRARY_Z_ALGORITHM_HPP

#include <iterator>
#include <vector>

namespace lib {

//! @tparam Container container type (deduced from parameter). operator[] and size(Container) must be defined.
//! @param src Source (container)
//! @return Vector contains the length of the longest common prefix
//! @note Time complexity: O(size(s))
template <typename Container>
[[nodiscard]] std::vector<int> z_algorithm(const Container& src) {
  const int size = static_cast<int>(std::size(src));

  std::vector<int> res(size);
  res[0] = size;

  for (int i = 1, l = 0, r = 0; i < size; ++i) {
    if (i <= r) {
      res[i] = std::min(r - i + 1, res[i - l]);
    }
    while (i + res[i] < size && src[i + res[i]] == src[res[i]]) {
      ++res[i];
    }
    if (i + res[i] - 1 > r) {
      l = i;
      r = i + res[i] - 1;
    }
  }

  return res;
}

}  // namespace lib

#endif  // CP_LIBRARY_Z_ALGORITHM_HPP

Back to top page