题目描述
对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
给定字符串A以及它的长度n，请返回最长回文子串的长度。
题解：
两个方法：
一个是经典暴力，这个大家应该都会
还一个是manacher（马拉车）
马拉车是专门处理回文串的算法
介绍两个变量
id：回文子串的中心位置
mx：回文子串的最后位置
p[i] = min(mx-i, p[2 * id - i])
p[i]：以i为中心的回文半径长度
当前，我们已经得到了 p[0…i-1]，想要计算出 p[i] 来。
红1为以 j 为中心的回文子串，红2为以 i 为中心的回文子串，红3为以 id 为中心的回文子串（首尾两端分别为mx的对称点和mx）。
那么，如果 mx 在 i 的右边，则我们可以通过已经计算出的 p[j] 来计算 p[i]，其中 j 与 i 的中心点为 id。这里分两种情况：
先直接令 p[i] 的回文子串就等于 p[j] 的回文子串，即红2长度等于红1，然后判断红2的末尾是否超过了 mx，如果没有超过，则说明 p[i] 就等于 p[j]。
为什么呢？
因为以 id 为中心的回文子串为红3，包含了红1和红2，而且红1和红2以 id 为中心，那么一定有红2=红1。并且已经知道，红1是以 j 为中心的最长子串，那么红2也肯定是以 i 为中心的最长子串。
如果红2的末尾超过了 mx，那么就只s能让 p[i] = mx - i了，即我可以保证至少半径到 mx 这个位置，是可以回文的，但是一旦往右超出了 mx，就不能保证了，剩下的只能用笨方法慢慢扩张来得到最长回文子串。
那如果红2的左边超出了mx的对称点，怎么办？不会出现这种情况的，因为红1的右边不会超过mx。如果超过了mx，那么在上一次迭代中，id应该更新为j，mx应该更新为 j+p[j]。在迭代中，会始终保证 mx 是所有已经得到的回文子串末端最靠右的位置。
另外，如果 mx 不在 i 的右边呢？那就利用不了红3的对称性了，只能使用笨方法慢慢扩张了。
代码：
class Palindrome {
public:
int p[100010], id = 0, mx = -1, maxx = -1;
int getLongestPalindrome(string A, int n) {
// write code here
string str = "@#";
for ( int i = 0; i < n; i++ ) {
str += A[i];
str += '#';
}
for ( int i = 0; i < str.size(); i++ ) {
if ( i < mx ) p[i] = min(p[ id * 2 - i], mx - i);
else p[i] = 1;
while ( str[i-p[i]] == str[i + p[i]]) p[i]++;
if ( p[i] + i > mx) {
id = i;
mx = p[i] + i;
}
maxx = max(maxx, p[i]-1);
}
return maxx;
}
};
京公网安备 11010502036488号