manacher
(src/string/manacher.hpp)

• View this file on GitHub
• Last update: 2024-11-09 02:46:49+09:00
• Include: #include "src/string/manacher.hpp"

manacher

vector<int> manacher(string s)

長さ $n$ の文字列 $s$ に含まれる回文の中心として考えられる位置は $2n - 1$ 個あります．
それぞれの位置 $i$ について $i$ を中心とする最長の回文の長さ $l_{i}$ を並べた長さ $2n - 1$ の配列 l を返します．
存在しない場合は $l_{i} = 0$ とします．

計算量

• $O(n)$

Depends on

• template (src/template/template.hpp)

Verified with

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

Code

#pragma once
#include "../template/template.hpp"
template <typename T>
vector<int> manacher(T s) {
    int n = (int)s.size();
    s.resize(2 * n - 1);
    for(int i = n - 1; i >= 0; --i) {
        s[2 * i] = s[i];
    }
    const auto d = *min_element(s.begin(), s.end());
    for(int i = 0; i < n - 1; ++i) {
        s[2 * i + 1] = d;
    }
    n = (int)s.size();
    vector<int> res(n);
    for(int i = 0, j = 0; i < n;) {
        while(i - j >= 0 and i + j < n and s[i - j] == s[i + j]) ++j;
        res[i] = j;
        int k = 1;
        while(i - k >= 0 and i + k < n and k + res[i - k] < j) {
            res[i + k] = res[i - k];
            ++k;
        }
        i += k, j -= k;
    }
    for(int i = 0; i < n; ++i) {
        if(((i ^ res[i]) & 1) == 0) --res[i];
    }
    return res;
}

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/string/manacher.hpp"
template <typename T>
vector<int> manacher(T s) {
    int n = (int)s.size();
    s.resize(2 * n - 1);
    for(int i = n - 1; i >= 0; --i) {
        s[2 * i] = s[i];
    }
    const auto d = *min_element(s.begin(), s.end());
    for(int i = 0; i < n - 1; ++i) {
        s[2 * i + 1] = d;
    }
    n = (int)s.size();
    vector<int> res(n);
    for(int i = 0, j = 0; i < n;) {
        while(i - j >= 0 and i + j < n and s[i - j] == s[i + j]) ++j;
        res[i] = j;
        int k = 1;
        while(i - k >= 0 and i + k < n and k + res[i - k] < j) {
            res[i + k] = res[i - k];
            ++k;
        }
        i += k, j -= k;
    }
    for(int i = 0; i < n; ++i) {
        if(((i ^ res[i]) & 1) == 0) --res[i];
    }
    return res;
}

Back to top page