verify/enumerate_palindromes.test.cpp

View this file on GitHub · Last update: 2026-07-25 03:07:16-07:00

Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

• manacher.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_palindromes

#include <bits/stdc++.h>
#include <cassert>

#include "manacher.hpp"

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	std::string S; std::cin >> S;
	int N = int(S.size());
	auto res = manacher(S);
	for (int i = 1; i <= 2*N-1; i++) {
		std::cout << res[i] << " \n"[i==2*N-1];
	}

	return 0;
}

#include <bits/stdc++.h>
#line 1 "verify/enumerate_palindromes.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/enumerate_palindromes

#line 5 "verify/enumerate_palindromes.test.cpp"

#line 2 "src/manacher.hpp"

#line 5 "src/manacher.hpp"

/**
 * manacher(S): return the maximum palindromic substring of S centered at each point
 *
 * Input: string (or vector) of length N (no restrictions on character-set)
 * Output: vector res of length 2*N+1
 *   For any 0 <= i <= 2*N:
 *   * i % 2 == res[i] % 2
 *   * the half-open substring S[(i-res[i])/2, (i+res[i])/2) is a palindrome of length res[i]
 *   * For odd palindromes, take odd i, and vice versa
 */
template <typename V> std::vector<int> manacher(const V& S) {
	int N = int(S.size());
	std::vector<int> res(2*N+1, 0);
	for (int i = 1, j = -1, r = 0; i < 2*N; i++, j--) {
		if (i > r) {
			r = i+1, res[i] = 1;
		} else {
			res[i] = res[j];
		}
		if (i+res[i] >= r) {
			int b = r>>1, a = i-b;
			while (a > 0 && b < N && S[a-1] == S[b]) {
				a--, b++;
			}
			res[i] = b-a, j = i, r = b<<1;
		}
	}
	return res;
}

/**
 * manacher_odd(S): return the maximum palindromic substring of S centered at each point
 *
 * Input: string (or vector) of length N (no restrictions on character-set)
 * Output: vector res of length N
 *   For any 0 <= i < N:
 *   * the half-open substring S[i-res[i], i+res[i]] is a palindrome of length 2*res[i]+1
 */
template <typename V> std::vector<int> manacher_odd(const V& S) {
	int N = int(S.size());
	std::vector<int> res(N);
	for (int i = 1, j = -1, r = 0; i < N; i++, j--) {
		if (i > r) {
			r = i, res[i] = 0;
		} else {
			res[i] = res[j];
		}
		if (i+res[i] >= r) {
			int b = r, a = 2*i-r;
			while (a-1 >= 0 && b+1 < N && S[a-1] == S[b+1]) {
				a--, b++;
			}
			res[i] = b-i, j = i, r = b;
		}
	}
	return res;
}
#line 7 "verify/enumerate_palindromes.test.cpp"

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	std::string S; std::cin >> S;
	int N = int(S.size());
	auto res = manacher(S);
	for (int i = 1; i <= 2*N-1; i++) {
		std::cout << res[i] << " \n"[i==2*N-1];
	}

	return 0;
}

// clang-format off
// @formatter:off
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#pragma GCC diagnostic ignored "-Wmultistatement-macros"
#include <bits/stdc++.h>
// src/manacher.hpp
template<typename V>std::vector<int>manacher(const V&S){
int N=int(S.size());
std::vector<int>res(2*N+1,0);
for(int i=1,j=-1,r=0;i<2*N;i++,j--){
if(i>r){
r=i+1,res[i]=1;
}else{
res[i]=res[j];
}
if(i+res[i]>=r){
int b=r>>1,a=i-b;
while(a>0&&b<N&&S[a-1]==S[b]){
a--,b++;
}
res[i]=b-a,j=i,r=b<<1;
}
}
return res;
}
template<typename V>std::vector<int>manacher_odd(const V&S){
int N=int(S.size());
std::vector<int>res(N);
for(int i=1,j=-1,r=0;i<N;i++,j--){
if(i>r){
r=i,res[i]=0;
}else{
res[i]=res[j];
}
if(i+res[i]>=r){
int b=r,a=2*i-r;
while(a-1>=0&&b+1<N&&S[a-1]==S[b+1]){
a--,b++;
}
res[i]=b-i,j=i,r=b;
}
}
return res;
}
// verify/enumerate_palindromes.test.cpp
int main(){
std::ios_base::sync_with_stdio(false),std::cin.tie(nullptr);
std::string S;std::cin>>S;
int N=int(S.size());
auto res=manacher(S);
for(int i=1;i<=2*N-1;i++){
std::cout<<res[i]<<" \n"[i==2*N-1];
}
return 0;
}
#pragma GCC diagnostic pop
// clang-format on
// @formatter:on

Test cases

Env	Name	Status	Elapsed	Memory
g++-sanitizer	all_same_00	AC	68 ms	16 MB
g++-sanitizer	all_same_01	AC	66 ms	16 MB
g++-sanitizer	all_same_02	AC	80 ms	16 MB
g++-sanitizer	all_same_03	AC	65 ms	16 MB
g++-sanitizer	all_same_04	AC	66 ms	16 MB
g++-sanitizer	example_00	AC	10 ms	8 MB
g++-sanitizer	example_01	AC	14 ms	8 MB
g++-sanitizer	example_02	AC	11 ms	8 MB
g++-sanitizer	example_03	AC	14 ms	8 MB
g++-sanitizer	max_random_00	AC	62 ms	15 MB
g++-sanitizer	max_random_01	AC	59 ms	16 MB
g++-sanitizer	max_random_02	AC	56 ms	16 MB
g++-sanitizer	max_random_03	AC	59 ms	16 MB
g++-sanitizer	max_random_04	AC	66 ms	16 MB
g++-sanitizer	random_00	AC	48 ms	14 MB
g++-sanitizer	random_01	AC	61 ms	16 MB
g++-sanitizer	random_02	AC	18 ms	9 MB
g++-sanitizer	random_03	AC	52 ms	15 MB
g++-sanitizer	random_04	AC	53 ms	12 MB
g++-sanitizer	small_00	AC	13 ms	8 MB
g++-sanitizer	small_01	AC	11 ms	8 MB
g++-sanitizer	small_02	AC	13 ms	8 MB
g++-sanitizer	small_03	AC	13 ms	8 MB
g++-sanitizer	small_04	AC	11 ms	8 MB
g++	all_same_00	AC	39 ms	8 MB
g++	all_same_01	AC	39 ms	8 MB
g++	all_same_02	AC	41 ms	8 MB
g++	all_same_03	AC	36 ms	8 MB
g++	all_same_04	AC	38 ms	8 MB
g++	example_00	AC	2 ms	4 MB
g++	example_01	AC	2 ms	3 MB
g++	example_02	AC	2 ms	4 MB
g++	example_03	AC	2 ms	4 MB
g++	max_random_00	AC	35 ms	8 MB
g++	max_random_01	AC	34 ms	8 MB
g++	max_random_02	AC	36 ms	8 MB
g++	max_random_03	AC	36 ms	8 MB
g++	max_random_04	AC	36 ms	8 MB
g++	random_00	AC	29 ms	7 MB
g++	random_01	AC	32 ms	8 MB
g++	random_02	AC	6 ms	4 MB
g++	random_03	AC	31 ms	7 MB
g++	random_04	AC	21 ms	6 MB
g++	small_00	AC	3 ms	4 MB
g++	small_01	AC	2 ms	3 MB
g++	small_02	AC	2 ms	4 MB
g++	small_03	AC	2 ms	4 MB
g++	small_04	AC	2 ms	3 MB

Back to top page