Manacher算法

#include<bits/stdc++.h>
using namespace std;
 
char  s[3000],c;
int  sj = 0, p[3000] = { 0 },mx=0,id,len=1;

//  p[i]:以s[i]为中心回文串单向扩张长度
//  id:最大回文子串中心位置
//  mx:最大回文子串右边界 & mx = id+p[id] ; 

int main() {
	s[sj++] = '\n';
	while (scanf("%c",&c)!=EOF) {
		s[sj++] = c;
		s[sj++] = '\n';          //s的首尾字符要一致，不然偶数串错误
	}
	s[sj]  = '\0';
	for (int i = 1; i < sj; i++) {
		if (i < mx)    p[i] = min(p[id * 2 - i], mx - id);
        //第一个if为第一类情况，大串套小串，而且对称位置的小串已经算出来了。
		else p[i] = 1;
        //不然就是初始为1赋值
		while (s[i - p[i]] == s[i + p[i]])++p[i];
        //以s[i]为中心向两边拓展
		if (p[id] < p[i]) {
			id = i;
			mx = p[i] + i;
		}
		len = max(len, p[i] - 1);//更新最大值
	}
	cout << len;
	return 0;
}