P3805 【模板】manacher 算法

#include <iostream>
#include <string>

using namespace std;

const int MaxN = 1.1e7 + 10;

int d[3][MaxN], n, ans;
string s;

void G(int f, int x) {  // 自力更生
  while (x - d[f][x] + f - 1 >= 0 && x + d[f][x] < n && s[x - d[f][x] + f - 1] == s[x + d[f][x]]) {
    d[f][x]++;
  }
  d[f][x]--;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> s, n = s.size();
  for (int i = 0, l = 0, r = -1; i < n; i++) {                         // r 好像必需是-1，为了0除可以自力更生
    d[1][i] = i > r ? 1 : min(d[1][l + (r - i)], r - i + 1), G(1, i);  // 自力更生或是用之前已经算好的
    if (i + d[1][i] > r) {
      r = i + d[1][i], l = i - d[1][i];
    }
    ans = max(ans, d[1][i] * 2 + 1);
  }
  for (int i = 0, l = 0, r = -1; i < n; i++) {
    d[2][i] = i > r ? 1 : min(d[2][l + (r - i - 1)], r - i - 1), G(2, i);
    if (i + d[2][i] > r) {
      r = i + d[2][i], l = i - d[2][i] + 1;
    }
    ans = max(ans, d[2][i] * 2);
  }
  cout << ans << '\n';
  return 0;
}