5# Longest Palindromic Substring

弱鸡进城纪实。

弱🐔就是这样，总是觉得什么都很牛逼想记录下来，总是觉得自己low弱，对，我就是个弱🐔，今天又来把大神屌炸天的东西写一写，免得忘了，嗯。

题呢，很简单，#5 Longest Palindromic Substring，简单讲就是求一个字符串的最长回文子字符串。

我的思路是搜索，对于字符串中的每一个字符，考察其作为回文子串中心时对应的回文子串长度，遍历结束，得到最长的回文子串。在考察回文子串的时候，需要对于其回文子串是偶数长度还是奇数长度进行区别考察。

思路很简单，实现起来也不复杂，整个复杂度是O(N^2)，确实也AC了，但是我在后来上网找解法的时候，发现了一种O(N)的方法，当时就惊呆了，赶紧好好地看了一下，这篇博客的主要目的也就是记录这个算法：

Manacher’s ALGORITHM: O(n)时间求字符串的最长回文子串

该算法的核心思想有两点，一是其对待求字符串进行的预处理，使处理过程无需对奇偶性做出考量；二是其利用一个很巧妙的结论，不断地重用已有的结果，达到简化运算量的作用。

下面就具体来说下这个算法是怎么做到的（大部分来自这里）：

首先对字符串进行预处理，用特殊字符将其填充至偶数个字符数，例如“123”填充至“$#1#2#3#*”，首尾选择特殊字符以标示开始结束（或者别的方法也行）。

然后用一个数组P[i]来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]，也就是把该回文串“对折”以后的长度）。如：

S  #1#2#2#1#2#3#2#1#
P  12125214121612121

显见的，P[i]-1的最大值就是我们要求的最长回文子串的长度。

那么，如何计算P[i]？

首先我们需要先说明一个关键的不等式：

P[i] >= MIN(P[2*id-i], mx-i)

• id是当前最长回文子串的中心
• mx是当前最长回文子串的扩张大小
• i是当前考察的字符位置
• j=2*id-i是i相对于id对称的点

那么这个不等式的含义就是，P[i]或者等于P[j]，或者大于或等于mx-i。

为了加深理解，画个图出来就很直观了：

当前最长子串内，关于中点对称的两点(j,id,i)，如果已经经过的点j上，P[j]小于mx-i，那么P[i]=P[j]。

当前最长子串内，关于中点id对称的两点(j,id,i)，如果已经经过的点j上，P[j]大于mx-i，那么P[i]至少等于mx-i。

而对于mx小于等于i(j)的情况，我们没有办法做出任何假设，只能认为这个时候P[i]=1了。

OK，到这里，最重要的三点已经解释清楚了，那么接下来我们就可以写出如下的计算P[i]的代码了：

//输入，并处理得到字符串s
int p[1000], mx = 0, id = 0;
//初始化P数组
memset(p, 0, sizeof(p));
//遍历S字符数组
for (i = 1; s[i] != '\0'; i++) {
    //核心点，p[i]的值通过历史值进行初始化。
    p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
    //对p[i]进行更新
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    //如果p[i]+i的范围比mx更大，那么后续的点就需要在这个新的范围内进行考察了。
    if (i + p[i] > mx) {
        mx = i + p[i];
        id = i;
    }
}
//找出p[i]中最大的

OK，到此为止这个算法就记录的差不多了，其实主要的思想还是复用之前算出来的结果，达到简化运算的目的，这个算法在while循环上省了很多功夫。

整个复杂度不太好算，既然他说是O(N)那就是O(N)吧。哈哈。