verify/str/zalgorithm.test.cpp

View this file on GitHub
Last update: 2024-06-14 20:43:15+08:00
Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

lib/str/z.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include <iostream>
#include <string>
#include "lib/str/z.hpp"

int main()
{
  std::string s;
  std::cin >> s;
  auto res = z_algorithm(s);
  res.pop_back();
  for (auto i : res) std::cout << i << " ";
  std::cout << std::endl;
}

#line 1 "verify/str/zalgorithm.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include <iostream>
#include <string>
#line 1 "lib/str/z.hpp"
#include <vector>
#line 3 "lib/str/z.hpp"

std::vector<int> z_algorithm(const std::string &s)
{
  int n = s.size();
  std::vector<int> z(n + 1);
  z[0] = n;
  int l = 0, r = 0;
  for (int i = 1; i <= n; i++) {
    int t = 0;
    if (i <= r) t = std::min(z[i - l], r - i);
    while (i + t < n && s[t] == s[i + t]) t++;
    z[i] = t;
    if (i + z[i] > r) {
      l = i;
      r = i + z[i];
    }
  }
  return z;
}
#line 6 "verify/str/zalgorithm.test.cpp"

int main()
{
  std::string s;
  std::cin >> s;
  auto res = z_algorithm(s);
  res.pop_back();
  for (auto i : res) std::cout << i << " ";
  std::cout << std::endl;
}