test/hackerrank/cutting-the-string.zalgo.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://www.hackerrank.com/contests/101hack50/challenges/cutting-the-string

Depends on

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

Code

// competitive-verifier: PROBLEM https://www.hackerrank.com/contests/101hack50/challenges/cutting-the-string
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// c++14 までだった

#include <iostream>
#include <string>
#include "src/String/z_algorithm.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 string s;
 cin >> s;
 int N= s.length();
 long long ans= 0;
 for (int i= 0; i < N; ++i) {
  auto z= z_algorithm(s.substr(i));
  auto p= z_to_kmp(z);
  int n= p.size();
  for (int j= 0; j < n; ++j) p[j]= j - p[j];
  for (int j= 1; j < n; ++j) {
   if (j % p[j] == 0 && j >= p[j] * 2) ans+= (j / p[j] - 1) * 2;
   ans+= 1;
  }
 }
 cout << ans << '\n';
 return 0;
}

#line 1 "test/hackerrank/cutting-the-string.zalgo.test.cpp"
// competitive-verifier: PROBLEM https://www.hackerrank.com/contests/101hack50/challenges/cutting-the-string
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// c++14 までだった

#include <iostream>
#include <string>
#line 2 "src/String/z_algorithm.hpp"
#include <vector>
#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 9 "test/hackerrank/cutting-the-string.zalgo.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 string s;
 cin >> s;
 int N= s.length();
 long long ans= 0;
 for (int i= 0; i < N; ++i) {
  auto z= z_algorithm(s.substr(i));
  auto p= z_to_kmp(z);
  int n= p.size();
  for (int j= 0; j < n; ++j) p[j]= j - p[j];
  for (int j= 1; j < n; ++j) {
   if (j % p[j] == 0 && j >= p[j] * 2) ans+= (j / p[j] - 1) * 2;
   ans+= 1;
  }
 }
 cout << ans << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00	AC	5 ms	4 MB
g++-13	01	AC	118 ms	4 MB
g++-13	02	AC	172 ms	4 MB
g++-13	03	AC	100 ms	4 MB
g++-13	04	AC	157 ms	4 MB
g++-13	05	AC	6 ms	4 MB
g++-13	06	AC	8 ms	4 MB
g++-13	07	AC	157 ms	4 MB
g++-13	08	AC	36 ms	4 MB
g++-13	09	AC	26 ms	4 MB
g++-13	10	AC	5 ms	4 MB
g++-13	11	AC	9 ms	4 MB
g++-13	12	AC	74 ms	4 MB
g++-13	13	AC	7 ms	4 MB
g++-13	14	AC	17 ms	4 MB
g++-13	15	AC	140 ms	4 MB
g++-13	16	AC	55 ms	4 MB
g++-13	17	AC	92 ms	4 MB
g++-13	18	AC	66 ms	4 MB
g++-13	19	AC	8 ms	4 MB
g++-13	20	AC	141 ms	4 MB
g++-13	21	AC	141 ms	4 MB
g++-13	22	AC	35 ms	4 MB
g++-13	23	AC	136 ms	4 MB
g++-13	24	AC	143 ms	4 MB
g++-13	25	AC	6 ms	4 MB
g++-13	26	AC	88 ms	4 MB
g++-13	27	AC	10 ms	4 MB
g++-13	28	AC	32 ms	4 MB
g++-13	29	AC	140 ms	4 MB
g++-13	30	AC	7 ms	4 MB
g++-13	31	AC	32 ms	4 MB
g++-13	32	AC	14 ms	4 MB
g++-13	33	AC	98 ms	4 MB
g++-13	34	AC	96 ms	4 MB
g++-13	35	AC	49 ms	4 MB
g++-13	36	AC	14 ms	4 MB
g++-13	37	AC	143 ms	4 MB
g++-13	38	AC	24 ms	4 MB
g++-13	39	AC	138 ms	4 MB
g++-13	40	AC	7 ms	4 MB
g++-13	41	AC	192 ms	4 MB
g++-13	42	AC	230 ms	4 MB
g++-13	43	AC	144 ms	4 MB
g++-13	44	AC	159 ms	4 MB
g++-13	45	AC	161 ms	4 MB
g++-13	46	AC	157 ms	4 MB
g++-13	47	AC	156 ms	4 MB
g++-13	48	AC	158 ms	4 MB
g++-13	49	AC	159 ms	4 MB
g++-13	50	AC	161 ms	4 MB
g++-13	51	AC	161 ms	4 MB
g++-13	52	AC	158 ms	4 MB
g++-13	53	AC	159 ms	4 MB
g++-13	54	AC	162 ms	4 MB
g++-13	55	AC	158 ms	4 MB
g++-13	56	AC	156 ms	4 MB
g++-13	57	AC	157 ms	4 MB
g++-13	58	AC	161 ms	4 MB
g++-13	59	AC	160 ms	4 MB
g++-13	60	AC	157 ms	4 MB
g++-13	61	AC	156 ms	4 MB
g++-13	62	AC	158 ms	4 MB
g++-13	63	AC	161 ms	4 MB
g++-13	64	AC	156 ms	4 MB
clang++-18	00	AC	5 ms	4 MB
clang++-18	01	AC	114 ms	4 MB
clang++-18	02	AC	196 ms	4 MB
clang++-18	03	AC	114 ms	4 MB
clang++-18	04	AC	180 ms	4 MB
clang++-18	05	AC	7 ms	4 MB
clang++-18	06	AC	9 ms	4 MB
clang++-18	07	AC	180 ms	4 MB
clang++-18	08	AC	43 ms	4 MB
clang++-18	09	AC	27 ms	4 MB
clang++-18	10	AC	5 ms	4 MB
clang++-18	11	AC	10 ms	4 MB
clang++-18	12	AC	71 ms	4 MB
clang++-18	13	AC	7 ms	4 MB
clang++-18	14	AC	20 ms	4 MB
clang++-18	15	AC	133 ms	4 MB
clang++-18	16	AC	64 ms	4 MB
clang++-18	17	AC	89 ms	4 MB
clang++-18	18	AC	65 ms	4 MB
clang++-18	19	AC	10 ms	4 MB
clang++-18	20	AC	114 ms	4 MB
clang++-18	21	AC	130 ms	4 MB
clang++-18	22	AC	29 ms	4 MB
clang++-18	23	AC	127 ms	4 MB
clang++-18	24	AC	135 ms	4 MB
clang++-18	25	AC	6 ms	4 MB
clang++-18	26	AC	73 ms	4 MB
clang++-18	27	AC	9 ms	4 MB
clang++-18	28	AC	27 ms	4 MB
clang++-18	29	AC	131 ms	4 MB
clang++-18	30	AC	7 ms	4 MB
clang++-18	31	AC	28 ms	4 MB
clang++-18	32	AC	13 ms	4 MB
clang++-18	33	AC	84 ms	4 MB
clang++-18	34	AC	78 ms	4 MB
clang++-18	35	AC	42 ms	4 MB
clang++-18	36	AC	13 ms	4 MB
clang++-18	37	AC	133 ms	4 MB
clang++-18	38	AC	24 ms	4 MB
clang++-18	39	AC	115 ms	4 MB
clang++-18	40	AC	7 ms	4 MB
clang++-18	41	AC	152 ms	4 MB
clang++-18	42	AC	218 ms	4 MB
clang++-18	43	AC	123 ms	4 MB
clang++-18	44	AC	163 ms	4 MB
clang++-18	45	AC	164 ms	4 MB
clang++-18	46	AC	164 ms	4 MB
clang++-18	47	AC	159 ms	4 MB
clang++-18	48	AC	161 ms	4 MB
clang++-18	49	AC	165 ms	4 MB
clang++-18	50	AC	163 ms	4 MB
clang++-18	51	AC	168 ms	4 MB
clang++-18	52	AC	159 ms	4 MB
clang++-18	53	AC	160 ms	4 MB
clang++-18	54	AC	169 ms	4 MB
clang++-18	55	AC	162 ms	4 MB
clang++-18	56	AC	162 ms	4 MB
clang++-18	57	AC	165 ms	4 MB
clang++-18	58	AC	162 ms	4 MB
clang++-18	59	AC	164 ms	4 MB
clang++-18	60	AC	162 ms	4 MB
clang++-18	61	AC	160 ms	4 MB
clang++-18	62	AC	165 ms	4 MB
clang++-18	63	AC	167 ms	4 MB
clang++-18	64	AC	161 ms	4 MB

Back to top page