test/library_checker/string/enumerate_palindromes.test.cpp

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

Depends on

• Manacher (lib/string/manacher.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/string/manacher.hpp"

int main(){
    string s; cin >> s;
    int n = s.size();
    string t = "";
    for(int i = 0; i < n; i++){
        t += s[i];
        if(i < n - 1) t += '$';
    }
    vector<int> m1 = manacher(s), m2 = manacher(t);
    for(int i = 0; i < 2 * n - 1; i++){
        int ans;
        if(i % 2 == 0){
            ans = 2 * m1[i / 2] - 1;
        }else{
            ans = m2[i] / 2 * 2;
        }
        if(i >= 1) cout << " ";
        cout << ans;
    }
    cout << "\n";
}

#line 1 "test/library_checker/string/enumerate_palindromes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/string/manacher.hpp"

/**
 * @brief Manacher
 * @docs docs/string/manacher.md
 */

template <typename T>
vector<int> manacher(const T &s){
    int n = s.size();
    vector<int> rad(n);
    int i = 0, j = 0;
    while(i < n){
        while(i - j >= 0 && i + j < (int) s.size() && s[i - j] == s[i + j]){
            j++;
        }
        rad[i] = j;
        int k = 1;
        while(i - k >= 0 && i + k < n && k + rad[i - k] < j){
            rad[i + k] = rad[i - k];
            k++;
        }
        i += k;
        j -= k;
    }
    return rad;
}

struct PalindromeCheck{
    const string s;
    string t;
    int n;
    vector<int> mana;

    PalindromeCheck(const string &str) : s(str){
        n = s.size();
        t = "$";
        for(int i = 0; i < n; i++){
            t += s[i];
            t += "$";
        }
        mana = manacher(t);
    }

    // [l, r)
    bool isPalindrome(int l, int r) const {
        int mid = l + r;
        return r * 2 - mid - 1 < mana[mid];
    }
};
#line 6 "test/library_checker/string/enumerate_palindromes.test.cpp"

int main(){
    string s; cin >> s;
    int n = s.size();
    string t = "";
    for(int i = 0; i < n; i++){
        t += s[i];
        if(i < n - 1) t += '$';
    }
    vector<int> m1 = manacher(s), m2 = manacher(t);
    for(int i = 0; i < 2 * n - 1; i++){
        int ans;
        if(i % 2 == 0){
            ans = 2 * m1[i / 2] - 1;
        }else{
            ans = m2[i] / 2 * 2;
        }
        if(i >= 1) cout << " ";
        cout << ans;
    }
    cout << "\n";
}

Back to top page