test/string/Manacher.test.cpp

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

Depends on

• Manacher's algorithm (src/string/Manacher.hpp)
• test/template.hpp

Code

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

int main() {
   cin.tie(0)->sync_with_stdio(0);
   string S;
   cin >> S;
   const ll N = sz(S);
   string T(N * 2 + 1, '$');
   rep(i, 0, N) T[i * 2 + 1] = S[i];
   auto r = manacher(T);
   rep(i, 1, N * 2) {
      if(i & 1) cout << r[i] - 1 << " \n"[i + 1 == N * 2];
      else cout << r[i] - 1 << ' ';
   }
}

#line 1 "test/string/Manacher.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_palindromes
#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/Manacher.hpp"
// 各位置での回文半径を求める
// aaabaaa -> 1214121
// 偶数長の回文を含めて直径を知るには，N+1 個の $ を挿入して 1 を引く
// $a$a$a$b$a$a$a$ -> 123432181234321
auto manacher(string s) {
   ll n = sz(s), i = 0, j = 0;
   V<ll> r(n);
   while(i < n) {
      while(i >= j && i + j < n && s[i - j] == s[i + j]) j++;
      r[i] = j;
      ll k = 1;
      while(i >= k && i + k < n && k + r[i - k] < j) {
         r[i + k] = r[i - k];
         k++;
      }
      i += k, j -= k;
   }
   return r;
}
#line 4 "test/string/Manacher.test.cpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   string S;
   cin >> S;
   const ll N = sz(S);
   string T(N * 2 + 1, '$');
   rep(i, 0, N) T[i * 2 + 1] = S[i];
   auto r = manacher(T);
   rep(i, 1, N * 2) {
      if(i & 1) cout << r[i] - 1 << " \n"[i + 1 == N * 2];
      else cout << r[i] - 1 << ' ';
   }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	50 ms	14 MB
g++	all_same_01	AC	50 ms	14 MB
g++	all_same_02	AC	51 ms	14 MB
g++	all_same_03	AC	61 ms	14 MB
g++	all_same_04	AC	51 ms	14 MB
g++	example_00	AC	2 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++	max_random_00	AC	43 ms	14 MB
g++	max_random_01	AC	46 ms	14 MB
g++	max_random_02	AC	48 ms	14 MB
g++	max_random_03	AC	48 ms	14 MB
g++	max_random_04	AC	48 ms	14 MB
g++	random_00	AC	38 ms	11 MB
g++	random_01	AC	44 ms	13 MB
g++	random_02	AC	8 ms	4 MB
g++	random_03	AC	40 ms	12 MB
g++	random_04	AC	26 ms	9 MB
g++	small_00	AC	2 ms	4 MB
g++	small_01	AC	2 ms	4 MB
g++	small_02	AC	2 ms	4 MB
g++	small_03	AC	2 ms	4 MB
g++	small_04	AC	2 ms	4 MB

Back to top page