最長回文 (Manacher's Algorithm)
(string/manacher.hpp)

• View this file on GitHub
• Last update: 2022-09-02 02:22:16+09:00
• Include: #include "string/manacher.hpp"

Manacher’s Algorithm

列が与えられたとき、各文字を中心とする回文の半径の最大値を求める。

vector<int> manacher(const T &A)

長さ $N$ の列 $A$ を引数に取り、長さ $N$ の配列を返す。

返り値の $i$ 番目の要素は、$A[i-k+1,i+k-1]$ が回文であるような $k$ の最大値である。

時間計算量は $O(N)$ である。

資料

あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

Verified with

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

Code

#pragma once
template <typename T>
vector<int> manacher(const T &A){
  int N = A.size();
  vector<int> ans(N, 0);
  int i = 0, j = 0;
  while (i < N){
    while (i >= j && i + j < N && A[i - j] == A[i + j]){
      j++;
    }
    ans[i] = j;
    int k = 1;
    while (i >= k && i + k < N && k + ans[i - k] < j){
      ans[i + k] = ans[i - k];
      k++;
    }
    i += k;
    j -= k;
  }
  return ans;
}

#line 2 "string/manacher.hpp"
template <typename T>
vector<int> manacher(const T &A){
  int N = A.size();
  vector<int> ans(N, 0);
  int i = 0, j = 0;
  while (i < N){
    while (i >= j && i + j < N && A[i - j] == A[i + j]){
      j++;
    }
    ans[i] = j;
    int k = 1;
    while (i >= k && i + k < N && k + ans[i - k] < j){
      ans[i + k] = ans[i - k];
      k++;
    }
    i += k;
    j -= k;
  }
  return ans;
}

Back to top page