test/string/Zalgorithm.test.cpp

• View this file on GitHub
• Last update: 2026-07-19 04:18:57+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

• Z Algorithm (src/string/Zalgorithm.hpp)
• test/template.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/zalgorithm
#include "test/template.hpp"
#include "src/string/Zalgorithm.hpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   string S;
   cin >> S;
   auto z = Z(S);
   rep(i, 0, sz(S)) cout << z[i] << " \n"[i + 1 == sz(S)];
}

#line 1 "test/string/Zalgorithm.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/zalgorithm
#line 1 "test/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
template<class T> using V = vector<T>;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define each(i, a) for(auto&& i : a)
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#line 1 "src/string/Zalgorithm.hpp"
// Z[i] := LCP(s, s[i:])
// abacaba -> 7010301
auto Z(string s) {
   ll n = sz(s), l = -1, r = -1;
   V<ll> z(n, n);
   rep(i, 1, n) {
      ll& x = z[i] = i < r ? min(r - i, z[i - l]) : 0;
      while(i + x < n && s[i + x] == s[x]) x++;
      if(i + x > r) l = i, r = i + x;
   }
   return z;
}
#line 4 "test/string/Zalgorithm.test.cpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   string S;
   cin >> S;
   auto z = Z(S);
   rep(i, 0, sz(S)) cout << z[i] << " \n"[i + 1 == sz(S)];
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	27 ms	8 MB
g++	all_same_01	AC	27 ms	8 MB
g++	all_same_02	AC	30 ms	8 MB
g++	all_same_03	AC	27 ms	8 MB
g++	all_same_04	AC	26 ms	8 MB
g++	binary_carry_00	AC	25 ms	8 MB
g++	binary_carry_01	AC	24 ms	8 MB
g++	example_00	AC	3 ms	4 MB
g++	example_01	AC	2 ms	4 MB
g++	example_02	AC	2 ms	4 MB
g++	example_03	AC	2 ms	4 MB
g++	fib_str_00	AC	25 ms	8 MB
g++	fib_str_01	AC	19 ms	7 MB
g++	fib_str_02	AC	19 ms	7 MB
g++	fib_str_03	AC	18 ms	7 MB
g++	fib_str_04	AC	25 ms	8 MB
g++	hack606_00	AC	3 ms	4 MB
g++	max_random_00	AC	25 ms	8 MB
g++	max_random_01	AC	27 ms	8 MB
g++	random_00	AC	21 ms	7 MB
g++	random_01	AC	25 ms	8 MB
g++	random_02	AC	5 ms	4 MB
g++	random_03	AC	24 ms	8 MB
g++	random_04	AC	15 ms	6 MB
g++	random_05	AC	18 ms	7 MB
g++	random_06	AC	24 ms	8 MB
g++	random_07	AC	7 ms	4 MB
g++	random_08	AC	14 ms	6 MB
g++	random_09	AC	8 ms	4 MB

Back to top page