Manecher算法总结

我是从牛客网上学的这个算法，听了一个小时左程云老师讲的课，然后结合网上的代码做的一点笔记和总结。
manecher算法不再区分字符串长度为奇数还是偶数，统一用一个特殊的字符扩充为2n级别的字符串。
例如：121
扩充后：#1#2#1#
按照牛客网左程云老师讲的内容，定义三个变量：
①pArr[]这是个整型数组，初始化为0，用来表示回文半径长度，包括自己
举个例子：#1#2#1#
数字2对应的pAarr[]为4
②pR初始化为0，用来表示回文半径扫到最右的下一个位置
③index当pR更新时，记录pR的回文中心

其二：
对于当前位置i关于index的对称位置为j,j在index的左边，i在index的右边。
j= index - (i-index) =2*index - i;
①j为中心对应的回文串半径左小在左大内
②j为中心对应的回文串半径左小再左大外
③左小与左大重合
④i在pR-1外面

为了防止越界，因为要比较开始的#,所以需要在最前面定义一个非#字符，比如$，最后面因为有字符串结束符’\0’，所以不用在后面添。
如果理解了这个算法，可以做做这道题：

是个简单的模板，我博客上也有这道题的题解。
最长对称子串
代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	string str,res="$#";
	getline(cin,str);
	//改造字符串 
	for(int i=0;i<str.size();i++){
		res +=str[i];
		res +="#";
	}
	//manacher算法
	vector<int> p(res.size(),0); //回文半径数组
	int r=0; //右边界
	int c=0; //第一次右边界对应的中心
	int maxL=0; //最大回文串的长度 
	for(int i=0;i<res.size();i++){
		p[i]= r>i ? min(p[2*c-i], r-i) : 1; //对p[i]做一次更新 
		
		while(res[i + p[i]] == res[i-p[i]]) p[i]++; //暴力扩 
		if(r < i+ p[i]){ //更新右边界 
 			r = i + p[i];
			c = i; 
		}
		if(p[i] > maxL) maxL = p[i]; 
	} 
	
	cout<<maxL-1<<endl; //因为回文半径是包含自身的 
	return 0;
} 

核心

int p[1005]
memset(p,0,sizeof(p)); 
void manecher(){
	int mx = 0,id = 0;
	for(int i=1;i<=len;i++){
		p[i] = mx >i?min(p[2*id-i],mx-i):1;//这里写得相对简洁，但是有点不容易理解 
		while(s[i+p[i]]==s[i-p[i]]) p[i]++;
		//及时更新最右位置和对应的中心点 
		if(mx<i+p[i]){
			mx = i+p[i];
			id = i;
		}
	}
}

值得推荐的算法详解