104 Manacher(马拉车)

视频链接：

 P3805 【模板】manacher 算法

#include 
#include 
#include 
using namespace std;

const int N = 3e7;
char a[N], s[N];
int p[N];

int main(){
  // 改造串
  scanf("%s", a+1);
  int n = strlen(a+1);
  int k = 0;
  s[0] = '$', s[++k] = '#';
  for(int i = 1; i <= n; i ++) 
    s[++k] = a[i], s[++k] = '#';
  n = k;
  
  // manacher算法
    int ans=0, r = 0, mid;
    for(int i=1; i<=n; i++){
        if(i<=r)p[i]=min(p[2*mid-i],r-i+1);
        while(s[i+p[i]]==s[i-p[i]]) p[i]++;
        if(i+p[i]>r) mid=i, r=i+p[i]-1;
        ans=max(ans, p[i]);
    }
  printf("%d\n", ans-1);
  return 0;
}