src/verify/yosupo-enumerate-palindromes.test.cpp

• View this file on GitHub
• Last update: 2026-03-15 03:09:02+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

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

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#include "../../cp-library/manacher"

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    auto ret = akTARDIGRADE13::manacher(s);
    int sz = ret.size();
    for (int i = 1; i < sz - 1; ++i) cout << ret[i] << ' ';
    cout << endl;
    return 0;
}

#line 1 "src/verify/yosupo-enumerate-palindromes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#line 2 "src/string/manacher.hpp"

#include <cassert>
#include <string>
#include <vector>

namespace akTARDIGRADE13 {

template <class T>
std::vector<int> manacher(const std::vector<T>& s) {
    int n = s.size();
    std::vector<int> ret(n << 1 | 1);
    int sz = ret.size();
    int i = 1, j = 1;
    while (i < sz) {
        while (j < i && i + j < (n << 1) && s[((i - j) >> 1) - 1] == s[(i + j) >> 1]) {
            j += 2;
        }
        ret[i] = j;
        if (j == 0) {
            i++;
            j = 1;
            continue;
        }
        int k = 1;
        while (k <= i && k + ret[i - k] < j) {
            ret[i + k] = ret[i - k];
            k++;
        }
        i += k;
        j -= k;
    }
    return ret;
}

std::vector<int> manacher(const std::string& s) {
    int n = s.size();
    std::vector<int> ret(n << 1 | 1);
    int sz = ret.size();
    int i = 1, j = 1;
    while (i < sz) {
        while (j < i && i + j < (n << 1) && s[((i - j) >> 1) - 1] == s[(i + j) >> 1]) {
            j += 2;
        }
        ret[i] = j;
        if (j == 0) {
            i++;
            j = 1;
            continue;
        }
        int k = 1;
        while (k <= i && k + ret[i - k] < j) {
            ret[i + k] = ret[i - k];
            k++;
        }
        i += k;
        j -= k;
    }
    return ret;
}

} // namespace akTARDIGRADE13
#line 3 "src/verify/yosupo-enumerate-palindromes.test.cpp"

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    auto ret = akTARDIGRADE13::manacher(s);
    int sz = ret.size();
    for (int i = 1; i < sz - 1; ++i) cout << ret[i] << ' ';
    cout << endl;
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	222 ms	24 MB
g++	all_same_01	AC	96 ms	24 MB
g++	all_same_02	AC	95 ms	24 MB
g++	all_same_03	AC	96 ms	24 MB
g++	all_same_04	AC	97 ms	24 MB
g++	example_00	AC	12 ms	20 MB
g++	example_01	AC	11 ms	18 MB
g++	example_02	AC	11 ms	20 MB
g++	example_03	AC	11 ms	18 MB
g++	max_random_00	AC	88 ms	24 MB
g++	max_random_01	AC	83 ms	24 MB
g++	max_random_02	AC	86 ms	24 MB
g++	max_random_03	AC	89 ms	24 MB
g++	max_random_04	AC	88 ms	24 MB
g++	random_00	AC	68 ms	23 MB
g++	random_01	AC	80 ms	23 MB
g++	random_02	AC	20 ms	19 MB
g++	random_03	AC	74 ms	23 MB
g++	random_04	AC	52 ms	19 MB
g++	small_00	AC	12 ms	18 MB
g++	small_01	AC	11 ms	20 MB
g++	small_02	AC	11 ms	18 MB
g++	small_03	AC	12 ms	20 MB
g++	small_04	AC	12 ms	18 MB

Back to top page