编程学习分享

对于求回文子串*会有以下三种方法：
1.暴力方法：

步骤：枚举所有子串O($n^2$)→ 检查回文O(n)→ 总复杂度O($n^3$)  
判断方法：双指针从两端向中间比对  
可优化的点：若中间子串非回文，则两端添加相同字符仍非回文,得到方法二。  

2.中心扩展法：

操作：枚举中心位置，向两侧扩展直到不匹配  
复杂度：枚举中心O(n)，扩展O(n)  
注意点：需区分奇偶长度中心  
可优化的点：可以在每一个字符之间（包括两端）添加字符,让总体变为偶数个。长度关系：新串最长回文子串长度m → 原串长度为m/2的向下取整  

3.马拉车

运算过程如下  
1.填充符号：在原字符串每个字符间插入特殊符号$，首尾也需添加，将奇偶长度统一为偶数  
2.数组定义：  
p[i]：记录处理后字符串以t[i]为中心的最长回文半径  
s[n]：原始字符串存储  
s[2n+5]：预处理后的字符串存储  
3.初始化参数：  
M：当前最长回文中心  
R：当前最长回文右边界  
初始值均设为0  
4.运行步骤：  
当i>R时暴力扩展：P[i]=1  
否则取对称点信息：p[i]=min(p[2M−i],R−i+1)   
中心扩展：检查t[i−p[i]]与t[i+p[i]]是否相等，循环扩展  
更新边界：若i+p[i]−1>R 则更新M=i，R=i+p[i]−1   
5.最终答案：max(p[i])−1   

复杂度为O(n)