Manacher
(lib/string/manacher.hpp)

• View this file on GitHub
• Last update: 2024-04-07 03:10:19+09:00
• Include: #include "lib/string/manacher.hpp"

Manacher

概要

文字列 $S$ のそれぞれの $i : (0 \leq i < \lvert S\lvert)$ について、$S[i]$ を中心とする最長回文の半径を求めます。

計算量

$\mathrm{O}(\lvert S\lvert)$

Verified with

• test/library_checker/string/enumerate_palindromes.test.cpp

Code

#pragma once

/**
 * @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 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];
    }
};

Back to top page