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

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

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

Code

/*
 * @title 文字列/Z algorithm
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/zalgorithm
 */

#include <iostream>
#include <string>
#include <utility>
#include <vector>

#include "emthrm/string/z_algorithm.hpp"

int main() {
  std::string s;
  std::cin >> s;
  const std::vector<int> ans = emthrm::z_algorithm(s);
  for (int i = 0; std::cmp_less(i, s.length()); ++i) {
    std::cout << ans[i] << " \n"[std::cmp_equal(i + 1, s.length())];
  }
  return 0;
}

#line 1 "test/string/z_algorithm.test.cpp"
/*
 * @title 文字列/Z algorithm
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/zalgorithm
 */

#include <iostream>
#include <string>
#include <utility>
#include <vector>

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



#include <algorithm>
#line 6 "include/emthrm/string/z_algorithm.hpp"

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


#line 13 "test/string/z_algorithm.test.cpp"

int main() {
  std::string s;
  std::cin >> s;
  const std::vector<int> ans = emthrm::z_algorithm(s);
  for (int i = 0; std::cmp_less(i, s.length()); ++i) {
    std::cout << ans[i] << " \n"[std::cmp_equal(i + 1, s.length())];
  }
  return 0;
}

Back to top page