test/string/z_algorithm/1.test.cpp

• View this file on GitHub
• Last update: 2021-08-11 13:32:54+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

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

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include <iostream>
#include <string>

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

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::string S;
  std::cin >> S;

  for (auto&& l : lib::z_algorithm(S))
    std::cout << l << ' ';

  std::cout << '\n';
}

#line 1 "test/string/z_algorithm/1.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include <iostream>
#include <string>

#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
#line 6 "test/string/z_algorithm/1.test.cpp"

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::string S;
  std::cin >> S;

  for (auto&& l : lib::z_algorithm(S))
    std::cout << l << ' ';

  std::cout << '\n';
}

Back to top page