原题描述
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example:
Input: “cbbd”
Output: “bb”
O(N)算法–Manacher算法
- 枚举字符串的每一个字串，起始有N种选择，结尾有N种选择，再判断是否回文遍历N次，所以时间复杂度为O(N^3)
- 枚举回文串的中点，枚举中点再判断是否是回文串，这样能把算法的时间复杂度降为O(N^2)
而Manacher算法可以在线性时间复杂度内求出一个字符串的最长回文字串，达到了理论上的下界
具体算法原理可以参见CSDN博客
其主要思想在于2点：
1. 利用在原字符串中插入分割符（分隔符的要求是不在原串中出现，一般情况下可以用#号）来统一考虑奇数长度和偶数长度的字符串，因为插入分割符之后可以保证回文字符串的长度一定是奇数。Tips：为了防止求解半径数组时越界，需要在前后再各加一个特殊字符比如@和$。
2. 巧妙的计算半径数组P[i]，这个计算过程利用到了回文串的对称性来保证已经搜索过的字符串不再重新搜索
C++代码
class Solution {
public:
string longestPalindrome(string s) {
string str = "", ans = "";
int len = s.length();
int pr = 0, p = 0;//pr是p的最长回文数边界的下一个index，pr=p+r[p];
int max_r = 0, max_mid = 0;
int r[2*len + 2];
str += '@'; //字符串开头增加一个特殊字符，防止越界
for (int i = 0; i < len; i++) {
str += '#';
str += s[i];
}
str += '#';
str += '$'; //字符串结尾加一个字符，防止越界
// 将原字符串扩展成#a#b#的形式，不用考虑回文串长度的奇偶性
for (int i = 1; i < 2 * len + 2; i++) {
if (i < pr) {//在r[j]和pr-i中取个小的
r[i] = (pr - i) > r[2*p - i] ? r[2*p - i] : (pr - i);
}
else {
r[i] = 1;//i >= pr 则从头开始匹配
}
while (str[i-r[i]] == str[i+r[i]]) {
r[i]++;
}
if ((i + r[i]) > pr) {//若新计算的回文串右端点位置大于pr，要更新p和pr的值
pr = i + r[i];
p = i;
}
if (max_r < r[i]) {
max_r = r[i];
max_mid = i;
}
}
ans = s.substr((max_mid - max_r) / 2, max_r - 1);
return ans;
}
};
Bug Free Procedure 从记事本直接写代码
2016.12.01 代码混乱+没有及时更新p和pr
1. 需要事先声明用于求最大长度字串的$ans, max_mid, max_r$和半径数组$r[]$
2. 当$i+r[i]$超过$pr$的时候没有更新$p$和$pr$
2016.12.04 函数使用错误
1. 需要事先声明$max_mid, max_r, r[]$
2. substr(起始位置index, 截取的长度)
2016.12.14 变量未申明+变量使用错误
1. 需要事先声明$p, pr, max_mid, max_r, r[]$
2. 要注意什么时候用s和str