最长回文子串
在知乎上看到一个回答，太强了，4ms解决leetcode上的该问题。
最长回文子串 - 力扣 (LeetCode) https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/
有什么浅显易懂的Manacher Algorithm讲解？ - 李其刚的回答 - 知乎
https://www.zhihu.com/question/37289584/answer/567220092
思路
这道题是经典的动态规划问题。要理解并不容易。
一般的动态规划，也没有4ms这么快。
manacher算法笑称马拉车算法。
为了方便地处理奇、偶回文串判别条件的区别，我们先将原串中所有字符之间增添一个原串中不曾出现的字符（我们假定为“#”）。
譬如说，abaaba，在增添后就变成了 #a#b#a#a#b#a，
这样，以#为中心的回文串，在原串中就是偶回文串。
我们考虑到，假如当前的i已经被包含在曾经被判断过的回文串内（即Mx>i)，那么它在这个回文串中相对应的那个字符Ma[2*ID-i]，应当已经被计算过以它为中心的回文串可以有多长了。那么，我们以第i位为中心的回文串长度，就有了第一个下限Mp[2*ID-i]。但是，我们考虑到，以Ma[2*ID-i]为中心的回文串，它可能延展到了以Ma[ID]为中心的回文串之外。这样我们就不能保证以Ma[i]为中心的回文串包括了以Ma[ID]为中心的回文串之外的部分。（因为Ma[i]未必有Ma[2*ID-i]这么大）所以我们得到了第二个下限Mx-i。
综上，在Mx>i时，我们就得到了Mp[i]=min(Mp[2*id-i],mx-i);
终于搞懂了扩展id与mx的方法，这样不断扩展，就可以把整个字符串包进来了。
/*
以#为中心的回文串，在原串中就是偶回文串。
数组Ma[i]：代表添加了“#”后的字符串。
数组Mp[i]：代表以字符串第i位为中心的回文串的最大半径。
变量Mx ：代表当前“已经匹配完毕的结尾最远的回文串”到达了Ma[]数组的第Mx位。
变量ID ：代表当前“已经匹配完毕的结尾最远的回文串”中心为Ma[]数组的第ID位。
Mp[i]-1即是该回文串的长度
*/
int mx = 0, id = 0;
for(int i= 0;i<l;i++){/*循环变量i代表了
当前正在判断Ma串的第i位为中心的回文子串最长长度。*/
Mp[i] = mx>i ? min(Mp[2*id-i],mx-i):1;//这一行最为关键
while(Ma[i+Mp[i]]==Ma[i-Mp[i]])
Mp[i]++;
if(i+Mp[i]>mx){
mx = i+Mp[i];
id = i;
}
}
感谢知乎的两位答主
AC代码
class Solution {
public:
string longestPalindrome(string s) {
int size = s.size();
if (size <= 1) return s;/*单字符回文子串就是它本身*/
int mp[2*size]={0}, mx = 2, id = 1, l=1, li = 1;/*如果是添加`#`字符，当然要翻倍了，因为字符串被加入了1倍数量的字符，但这里是假装修改s添加了字符
初试最右边界，设定为2，中心设定下标为1*/
for(int i=2; i < 2 * size - l; i++){
mp[i] = mx > i ? min(mp[2*id - i], mx - i) : 0;/*这里半径长度是从0开始加起*/
int left = (i-mp[i]-1)/2, right = (i+mp[i])/2;/*假装添加了字符的新字符串的左右边界，因为i和mp[i]是假装添加字符之后的概念，i的上限是2*size - l。实际取值要除以2*/
while(left >= 0 && right < size) {
if(left==right) mp[i]++;
else if(s[left] == s[right]) mp[i] = mp[i] + 2;/*因为s本身，并没有被添加，只有i与mp[i]按照添加过处理，或者说 如果真添加的#符，也没有做比较的意义，因为必定满足左右扩展的条件，必定+1，这里跳过#符，有回文。直接+2*/
else break;
left--;
right++;/*中心向左右扩展*/
}/*这里比起常规的一行解决，要复杂的多。*/
if(i+mp[i] > mx){/*这里是更新最右边界，与相应中心的地方*/
mx = i + mp[i];
id = i;
}
if(mp[i] > l){/*找最大的半径，也是找最大的长度*/
l = mp[i];/*mp[i]是加字字符串里的回文子串的半径长度，也就是原本字符串的回文串长度*/
li = i;/*记录中心*/
}
}
return s.substr((li-l+1)/2, l);/*返回该最长回文子串，(li-l+1)是加字串的回文子串的起点，/2变成，原本字符串的对应起点*/
}
};
思路
这道题是经典的动态规划问题。要理解并不容易。
一般的动态规划，也没有4ms这么快。
manacher算法笑称马拉车算法。
为了方便地处理奇、偶回文串判别条件的区别，我们先将原串中所有字符之间增添一个原串中不曾出现的字符（我们假定为“#”）。
譬如说，abaaba，在增添后就变成了 #a#b#a#a#b#a，
这样，以#为中心的回文串，在原串中就是偶回文串。
我们考虑到，假如当前的i已经被包含在曾经被判断过的回文串内（即Mx>i)，那么它在这个回文串中相对应的那个字符Ma[2*ID-i]，应当已经被计算过以它为中心的回文串可以有多长了。那么，我们以第i位为中心的回文串长度，就有了第一个下限Mp[2*ID-i]。但是，我们考虑到，以Ma[2*ID-i]为中心的回文串，它可能延展到了以Ma[ID]为中心的回文串之外。这样我们就不能保证以Ma[i]为中心的回文串包括了以Ma[ID]为中心的回文串之外的部分。（因为Ma[i]未必有Ma[2*ID-i]这么大）所以我们得到了第二个下限Mx-i。
综上，在Mx>i时，我们就得到了Mp[i]=min(Mp[2*id-i],mx-i);
终于搞懂了扩展id与mx的方法，这样不断扩展，就可以把整个字符串包进来了。
/*
以#为中心的回文串，在原串中就是偶回文串。
数组Ma[i]：代表添加了“#”后的字符串。
数组Mp[i]：代表以字符串第i位为中心的回文串的最大半径。
变量Mx ：代表当前“已经匹配完毕的结尾最远的回文串”到达了Ma[]数组的第Mx位。
变量ID ：代表当前“已经匹配完毕的结尾最远的回文串”中心为Ma[]数组的第ID位。
Mp[i]-1即是该回文串的长度
*/
int mx = 0, id = 0;
for(int i= 0;i<l;i++){/*循环变量i代表了
当前正在判断Ma串的第i位为中心的回文子串最长长度。*/
Mp[i] = mx>i ? min(Mp[2*id-i],mx-i):1;//这一行最为关键
while(Ma[i+Mp[i]]==Ma[i-Mp[i]])
Mp[i]++;
if(i+Mp[i]>mx){
mx = i+Mp[i];
id = i;
}
}
感谢知乎的两位答主
有什么浅显易懂的Manacher Algorithm讲解？ - 233 Magic的回答 - 知乎
https://www.zhihu.com/question/37289584/answer/71483487
有什么浅显易懂的Manacher Algorithm讲解？ - C加加编程思想的回答 - 知乎
https://www.zhihu.com/question/37289584/answer/370848679