test/library_checker/string/zalgorithm.test.cpp

View this file on GitHub
Last update: 2022-09-02 02:22:16+09:00
Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

Z Algorithm (string/z_algorithm.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include <bits/stdc++.h>
using namespace std;
#include "../../../string/z_algorithm.hpp"
int main(){
  string S;
  cin >> S;
  int N = S.size();
  vector<int> ans = z_algorithm(S);
  for (int i = 0; i < N; i++){
    cout << ans[i];
    if (i < N - 1){
      cout << ' ';
    }
  }
  cout << endl;
}

#line 1 "test/library_checker/string/zalgorithm.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include <bits/stdc++.h>
using namespace std;
#line 2 "string/z_algorithm.hpp"
template <typename T>
vector<int> z_algorithm(const T &A){
  int N = A.size();
  vector<int> Z(N, 0);
  for (int i = 1, j = 0; i < N; i++){
    if (i + Z[i - j] < j + Z[j]){
      Z[i] = Z[i - j];
    } else {
      int k = max(0, j + Z[j] - i);
      while (i + k < N && A[k] == A[i + k]){
        k++;
      }
      Z[i] = k;
      j = i;
    }
  }
  Z[0] = N;
  return Z;
}
#line 5 "test/library_checker/string/zalgorithm.test.cpp"
int main(){
  string S;
  cin >> S;
  int N = S.size();
  vector<int> ans = z_algorithm(S);
  for (int i = 0; i < N; i++){
    cout << ans[i];
    if (i < N - 1){
      cout << ' ';
    }
  }
  cout << endl;
}