Manacher

Code

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

/*
 * 文字 i を中心とする最長の回文の半径 = (全長 + 1) / 2
 */

vector<i64> manacher(string S) {
  vector<i64> R(S.size());
  int i = 0, j = 0;
  while (i < S.size()) {
    while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
    R[i] = j;
    int k = 1;
    while (i-k >= 0 && i+k < S.size() && k+R[i-k] < j) R[i+k] = R[i-k], ++k;
    i += k; j -= k;
  }
  return R;
}