test/yosupo/enumerate_palindromes.test.cpp

View this file on GitHub
Last update: 2024-01-07 22:05:53+09:00
Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

Manacher's Algorithm (string/manacher.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"

#include <bits/stdc++.h>

#include "../../string/manacher.hpp"
using namespace std;
using ll = long long;

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

    string S;
    cin >> S;
    auto ans = manacher(S);
    for (int i = 0; i < ans.size(); ++i) {
        if (i % 2 == 0)
            cout << 2 * ans[i] - 1;
        else
            cout << 2 * ans[i];
        if (i < ans.size() - 1)
            cout << " ";
        else
            cout << endl;
    }
}

#line 1 "test/yosupo/enumerate_palindromes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"

#include <bits/stdc++.h>

#line 5 "string/manacher.hpp"

std::vector<int> manacher(const std::string& s) {
    const int n = s.size();
    std::vector<int> vs(2 * n - 1);
    // odd length
    for (int i = 0, l = 0, r = -1; i < n; ++i) {
        int k = (i > r) ? 1 : std::min(vs[2 * (l + r - i)], r - i + 1);
        while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) ++k;
        vs[2 * i] = k;
        --k;
        if (i + k > r) {
            l = i - k;
            r = i + k;
        }
    }
    // even length
    for (int i = 1, l = 0, r = -1; i < n; ++i) {
        int k = (i > r) ? 0 : std::min(vs[2 * (l + r - i + 1) - 1], r - i + 1);
        while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) ++k;
        vs[2 * i - 1] = k;
        --k;
        if (i + k > r) {
            l = i - k - 1;
            r = i + k;
        }
    }
    return vs;
}
#line 6 "test/yosupo/enumerate_palindromes.test.cpp"
using namespace std;
using ll = long long;

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

    string S;
    cin >> S;
    auto ans = manacher(S);
    for (int i = 0; i < ans.size(); ++i) {
        if (i % 2 == 0)
            cout << 2 * ans[i] - 1;
        else
            cout << 2 * ans[i];
        if (i < ans.size() - 1)
            cout << " ";
        else
            cout << endl;
    }
}