test/yosupo_judge/zalgorithm.test.cpp

View this file on GitHub
Last update: 2022-12-22 01:59:18+09:00
Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

src/string/z_algorithm.hpp

Code

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

#include <bits/stdc++.h>
using namespace std;

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

int main() {
  string S;
  cin >> S;
  auto res = z_algorithm(S);
  for (int i = 0; i < res.size(); i++) {
    if (i != 0) {
      cout << " ";
    }
    cout << res[i];
  }
  cout << endl;
  return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/string/z_algorithm.hpp"

#line 4 "src/string/z_algorithm.hpp"
using namespace std;

template <typename T = int> vector<T> z_algorithm(string s) {
  int n = s.size();
  vector<T> res(n, 0);
  res[0] = n;
  int i = 1, j = 0;
  while (i < n) {
    while (i + j < n && s[j] == s[i + j]) {
      ++j;
    }
    res[i] = j;
    if (j == 0) {
      ++i;
      continue;
    }
    int k = 1;
    while (i + k < n && k + res[k] < j) {
      res[i + k] = res[k];
      ++k;
    }
    i += k;
    j -= k;
  }
  return res;
}
#line 7 "test/yosupo_judge/zalgorithm.test.cpp"

int main() {
  string S;
  cin >> S;
  auto res = z_algorithm(S);
  for (int i = 0; i < res.size(); i++) {
    if (i != 0) {
      cout << " ";
    }
    cout << res[i];
  }
  cout << endl;
  return 0;
}