最长回文子串

在知乎上看到一个回答，太强了，4ms解决leetcode上的该问题。

最长回文子串 - 力扣 (LeetCode)

有什么浅显易懂的Manacher Algorithm讲解？ - 李其刚的回答 - 知乎

思路

这道题是经典的动态规划问题。要理解并不容易。

一般的动态规划，也没有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
    
     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
    
     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的回答 - 知乎

有什么浅显易懂的Manacher Algorithm讲解？ - C加加编程思想的回答 - 知乎