Question
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Quick Navigation
SummarySolution
Approach #1 (Longest Common Substring) [Accepted]Approach #2 (Brute Force) [Time Limit Exceeded]Approach #3 (Dynamic Programming) [Accepted]Approach #4 (Expand Around Center) [Accepted]Approach #5 (Manacher's Algorithm) [Accepted]
问题：求最长回文子字符串
这里介绍一下五种方法：
方法1：最长公共子字符串的方法
解决时通常会犯的一个错误解法：对于字符串S，经过反转得到S'，然后求两者的公共子字符串。仅这样求解是错误的，以下是说明：
通常时，如S={c,a,b,a}和反转S'={a,b,a,c}。两个的公共子字符串是{a,b,a}，它也是答案的解。但是对于一些例子，如S={a,b,a,c,d,f,g,d,c,a,b,a}和它的
反转S'={a,b,a,c,d,g,f,d,c,a,b,a}，它们的公共子字符串是{a,b,a,c,d}，显然它不是答案。
可见，如果S的其他部分如果等于另外某一部分的子字符串反转，那么它得到的结果将不是答案。
对此，我们可以修改原来的算法：
每次我们找到候选的最长公共子字符串，我们都要检查一下该子字符串在S中的下标是否同S'的原始下标一致。如果一致，我们就更新目前所找的最长回文字符串，如果下标有异，我们就跳过这个字符串。
算法复杂度：
O
(
n2
)
方法2：暴力法（TLE）
显然，就是把所有可能的开始和结束位置组成的子字符串进行回文判断。
算法复杂度：时间复杂度O(n3)，因为有(2n)=2n(n−1)个字符串，每个字符串最多进行n次操作
空间复杂度：O（1）
方法3：动态规划（AC原文是这样的，但我试的时候，TLE了，不知道是否有错误）
定义一个二维数组P[n][n]，其中P[i][j]代表从i开始到j结束的子字符串是否是回文。
P(i,j)={true,if the substring Si…Sj is a palindromefalse,otherwise.
因此，我们得到以下递推式： P(i,j)=(P(i+1,j−1) and Si==Sj)
如果s[i]==s[j],则子字符串s[i,...,j]与子字符串s[i+1,...,j-1]的判断结果一样。
初始化时：p[i,i]=true，只有一个元素时，必是回文；两个元素时，p[i,i+1]=(s[i]==s[i+1]);
在此基础上，可以使用动态规划判断回文字符串了。
下面的代码，没有初始化两个元素的情况，但初始时如i>j,p[i,j]=true;解决了这一情况。
说明：TLE,没有通过
int n=s.size();
vector
> f(n);
int i,j,start,end;
for(i=0;i
=j)
f[i][j]=true;
else f[i][j]=false;
int len=1;
start=end=0;
for(j=1;j
方法4：以中心展开(AC)
我们观察到回文都是以中心为镜像的，因此一个回文可以围绕他的中心展开，而这样的中心有2n-1个。
也许，你会问为什么是2n-1而不是n个呢？因为一个回文的中心可能会在两个字母的中间。当回文的字符个数
是偶数时，如{a,b,b,a},那么它的中心就在两个b之间。因此，对于有n个字母的字符串，它有n(n个字母)
+
n-1(n个字母间的n-1个间隙)=2n-1个中心。
class Solution {
int expandAroundCenter(string s, int left, int right) {
int L = left;
int R = right;
while (L >= 0 && R < s.length() && s[L]==s[R]) {
L--;
R++;
}//循环结束时，最后边界的两个字符不再回文之内
return R - L -1;//R-L+1-2
}
public:
string longestPalindrome(string s) {
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
string str(s,start,end-start+1);
return str;
}
};
算法复杂度分析：时间复杂度O(n*n),空间复杂度O(1)
方法5:Manacher算法
时间复杂度O(n),技巧性很强,不太懂
string preProcess(string s)
{
int n = s.size();
if (n == 0) return "^$";
string ret = "^";
for (int i = 0; i < n; i++)
{
ret += "#";
ret+=s[i];
}
ret += "#$";
return ret;
}
public:
string longestPalindrome(string s) {
string T = preProcess(s);
int n = T.size();
vector
P(n); //int *P = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n-1; i++) {
int i_mirror = 2*C-i; // equals to i' = C - (i-C)
P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
P[i]++;
// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// Find the maximum element in P.
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n-1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
//delete[] P;
string str(s,(centerIndex - 1 - maxLen)/2,maxLen);
return str;
//return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
}
http://articles.leetcode.com/longest-palindromic-substring-part-ii/
转载请注明原文地址: https://ju.6miu.com/read-1125018.html
