test/string/manacher.test.cpp

View this file on GitHub
Last update: 2025-04-15 19:14:29+09:00
Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

string/Manacher.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#include "../../string/Manacher.hpp"
#include <iostream>

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string S;
    std::cin >> S;
    auto res = po167::Manacher(S);
    for (int i = 0; i < (int)res.size(); i++){
        std::cout << res[i] << ((int)(res.size()) == i + 1 ? "\n" : " ");
    }
}

#line 1 "test/string/manacher.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#line 2 "string/Manacher.hpp"
#include <vector>
#include <string>


// https://snuke.hatenablog.com/entry/2014/12/02/235837
namespace po167{
template<class T>

// input  : abaab
// output : 1 0 3 0 1 4 1 0 1
std::vector<int> Manacher(std::vector<T> &v){
    int N = v.size();
    std::vector<int> res(N * 2 + 1);
    int i = 0, j = 0;
    while (i < N * 2 + 1){
        while (i - j >= 0 && i + j < N * 2 + 1 
            && (((i + j) & 1) == 0 || v[(i - j) / 2] == v[(i + j) / 2])) j++;
        res[i] = j;
        int k = 1;
        while (i - k >= 0 && k + res[i - k] < j) res[i + k] = res[i - k], k++;
        i += k, j -= k;
    }
    res.pop_back();
    res.erase(res.begin());
    for (auto &x : res) x--;
    return res;
}

// input  : abaab
// output : 1 0 3 0 1 4 1 0 1
std::vector<int> Manacher(std::string &s){
    std::vector<int> v(s.size());
    for (int i = 0; i < (int)s.size(); i++) v[i] = s[i];
    return Manacher(v);
}
}
#line 3 "test/string/manacher.test.cpp"
#include <iostream>

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string S;
    std::cin >> S;
    auto res = po167::Manacher(S);
    for (int i = 0; i < (int)res.size(); i++){
        std::cout << res[i] << ((int)(res.size()) == i + 1 ? "\n" : " ");
    }
}