test/yosupo/z_algorithm.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

• Z-Algorithm (src/String/z_algorithm.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/zalgorithm
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <string>
#include <vector>
#include "src/String/z_algorithm.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 string s;
 cin >> s;
 vector<int> ans= z_algorithm(s);
 int N= s.length();
 for (int i= 0; i < N; i++) cout << ans[i] << " \n"[i == N - 1];
 return 0;
}

#line 1 "test/yosupo/z_algorithm.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/zalgorithm
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <string>
#include <vector>
#line 3 "src/String/z_algorithm.hpp"
#include <algorithm>
#line 5 "src/String/z_algorithm.hpp"
#include <tuple>
template <class String> std::vector<int> z_algorithm(const String &s) {
 const int n= s.size();
 if (n == 0) return {};
 std::vector<int> z(n);
 for (int i= 1, j= 0; i < n; ++i) {
  int &k= z[i];
  for (k= (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]); i + k < n && s[k] == s[i + k];) ++k;
  if (j + z[j] < i + z[i]) j= i;
 }
 return z[0]= n, z;
}
std::vector<int> z_to_kmp(const std::vector<int> &z) {
 const int n= z.size();
 std::vector<int> kmp(n + 1);
 kmp[0]= -1;
 for (int i= n; --i;) kmp[i + z[i]]= std::max(kmp[i + z[i]], z[i]);
 for (int i= n; i--;) kmp[i]= std::max(kmp[i], kmp[i + 1] - 1);
 return kmp;
}
namespace string_internal {
template <class String> auto run_enumerate_(const String &s, typename String::value_type a= 0) {
 using Run= std::tuple<int, int, int>;
 std::vector<Run> glb;
 auto rec= [&](auto rec, int l, int r) -> std::vector<Run> {
  if (r - l <= 1) return {};
  const int m= (l + r) / 2, lsz= m - l, rsz= r - m;
  std::vector<Run> run_l= lsz > 1 ? rec(rec, l, m) : std::vector<Run>(), run_r= rsz > 1 ? rec(rec, m, r) : std::vector<Run>();
  std::vector<typename String::value_type> rl(r - l + 1, a);
  std::copy(s.begin() + m, s.begin() + r, rl.begin()), std::copy(s.begin() + l, s.begin() + m, rl.begin() + rsz + 1);
  std::vector<int> zrl= z_algorithm(rl);
  std::reverse(rl.begin(), rl.end());
  std::vector<int> zrl_r= z_algorithm(rl);
  const int sz= rl.size();
  std::vector<Run> ret;
  auto push= [&](int b, int e, int p) { (b == l || e == r ? ret : glb).emplace_back(b, e, p); };
  std::vector<Run> run_m(rsz / 2 + 1);
  for (auto [b, e, p]: run_r) {
   if (b != m) ret.emplace_back(b, e, p);
   else run_m[p]= Run{b, e, p};
  }
  for (auto [b, e, p]: run_l)
   if (e != m) ret.emplace_back(b, e, p);
   else if (zrl[sz - p] == p) {
    if (std::get<2>(run_m[p])) push(b, std::get<1>(run_m[p]), p), run_m[p]= Run{};
    else push(b, m + p + zrl[p], p);
   } else push(b, m + zrl[sz - p], p);
  for (auto [b, e, p]: run_m)
   if (p) {
    if (zrl[sz - p] != p) push(m - zrl_r[sz - p], e, p);
    else if (2 * p > lsz || zrl[sz - 2 * p] < p) push(m - p - zrl_r[p], e, p);
   }
  for (int p= 1; p <= lsz; ++p)
   if (bool skpr= 2 * p <= rsz && zrl[p] >= p, skpl= 2 * p <= lsz && zrl[sz - 2 * p] >= p; zrl[sz - p] == p) {
    if (!skpl && !skpr) push(m - p - zrl_r[p], m + p + zrl[p], p);
   } else {
    if (!skpr)
     if (int b= m - zrl_r[sz - p], e= m + p + zrl[p]; e - b >= 2 * p) push(b, e, p);
    if (!skpl)
     if (int b= m - p - zrl_r[p], e= m + zrl[sz - p]; e - b >= 2 * p) push(b, e, p);
   }
  return ret;
 };
 std::vector<std::tuple<int, int, int>> runs= rec(rec, 0, s.size());
 std::copy(glb.begin(), glb.end(), std::back_inserter(runs)), std::sort(runs.begin(), runs.end()), runs.erase(std::unique(runs.begin(), runs.end(), [](auto &r1, auto &r2) { return std::get<0>(r1) == std::get<0>(r2) && std::get<1>(r1) == std::get<1>(r2); }), runs.end());
 int rn= runs.size(), n= s.size();
 glb.resize(rn);
 std::vector<int> pt(n);
 for (auto [l, r, p]: runs) ++pt[p];
 for (int i= 1; i < n; ++i) pt[i]+= pt[i - 1];
 for (int i= rn; i--;) glb[--pt[std::get<2>(runs[i])]]= {std::get<2>(runs[i]), std::get<0>(runs[i]), std::get<1>(runs[i])};
 return glb;
}
template <class Int, typename= std::enable_if_t<std::is_integral_v<Int>>> auto run_enumerate(const std::vector<Int> &s) { return run_enumerate_(s, *std::max_element(s.begin(), s.end()) + 1); }
template <class String> auto run_enumerate(const String &s) {
 auto v= s;
 std::sort(v.begin(), v.end()), v.erase(std::unique(v.begin(), v.end()), v.end());
 std::vector<int> t(s.size());
 for (int i= s.size(); i--;) t[i]= std::lower_bound(v.begin(), v.end(), s[i]) - v.begin();
 return run_enumerate_(t, v.size() + 1);
}
auto run_enumerate(const std::string &s) { return run_enumerate_(s); }
}
using string_internal::run_enumerate;
#line 8 "test/yosupo/z_algorithm.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 string s;
 cin >> s;
 vector<int> ans= z_algorithm(s);
 int N= s.length();
 for (int i= 0; i < N; i++) cout << ans[i] << " \n"[i == N - 1];
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	all_same_00	AC	38 ms	8 MB
g++-13	all_same_01	AC	38 ms	8 MB
g++-13	all_same_02	AC	38 ms	8 MB
g++-13	all_same_03	AC	38 ms	8 MB
g++-13	all_same_04	AC	37 ms	8 MB
g++-13	binary_carry_00	AC	29 ms	8 MB
g++-13	binary_carry_01	AC	30 ms	8 MB
g++-13	example_00	AC	5 ms	4 MB
g++-13	example_01	AC	5 ms	4 MB
g++-13	example_02	AC	5 ms	4 MB
g++-13	example_03	AC	5 ms	4 MB
g++-13	fib_str_00	AC	30 ms	8 MB
g++-13	fib_str_01	AC	24 ms	7 MB
g++-13	fib_str_02	AC	23 ms	6 MB
g++-13	fib_str_03	AC	22 ms	6 MB
g++-13	fib_str_04	AC	30 ms	8 MB
g++-13	hack606_00	AC	6 ms	4 MB
g++-13	max_random_00	AC	29 ms	8 MB
g++-13	max_random_01	AC	30 ms	8 MB
g++-13	random_00	AC	24 ms	7 MB
g++-13	random_01	AC	28 ms	7 MB
g++-13	random_02	AC	8 ms	4 MB
g++-13	random_03	AC	26 ms	7 MB
g++-13	random_04	AC	18 ms	6 MB
g++-13	random_05	AC	19 ms	6 MB
g++-13	random_06	AC	26 ms	7 MB
g++-13	random_07	AC	9 ms	4 MB
g++-13	random_08	AC	17 ms	6 MB
g++-13	random_09	AC	10 ms	4 MB
clang++-18	all_same_00	AC	32 ms	8 MB
clang++-18	all_same_01	AC	32 ms	8 MB
clang++-18	all_same_02	AC	32 ms	8 MB
clang++-18	all_same_03	AC	33 ms	8 MB
clang++-18	all_same_04	AC	38 ms	8 MB
clang++-18	binary_carry_00	AC	31 ms	8 MB
clang++-18	binary_carry_01	AC	30 ms	8 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	example_01	AC	5 ms	4 MB
clang++-18	example_02	AC	5 ms	4 MB
clang++-18	example_03	AC	5 ms	4 MB
clang++-18	fib_str_00	AC	28 ms	8 MB
clang++-18	fib_str_01	AC	23 ms	7 MB
clang++-18	fib_str_02	AC	22 ms	6 MB
clang++-18	fib_str_03	AC	21 ms	6 MB
clang++-18	fib_str_04	AC	29 ms	8 MB
clang++-18	hack606_00	AC	6 ms	4 MB
clang++-18	max_random_00	AC	28 ms	8 MB
clang++-18	max_random_01	AC	27 ms	8 MB
clang++-18	random_00	AC	23 ms	7 MB
clang++-18	random_01	AC	26 ms	7 MB
clang++-18	random_02	AC	8 ms	4 MB
clang++-18	random_03	AC	24 ms	7 MB
clang++-18	random_04	AC	18 ms	6 MB
clang++-18	random_05	AC	19 ms	6 MB
clang++-18	random_06	AC	28 ms	7 MB
clang++-18	random_07	AC	10 ms	4 MB
clang++-18	random_08	AC	17 ms	6 MB
clang++-18	random_09	AC	11 ms	4 MB

Back to top page