最长接续回文串（Longest Palindromic Substring）

最长连续回文串（Longest Palindromic Substring）
题目： 

Given a string S, find the longest palindromic substring in S.

给出一个字符串S，找到一个最长的连续回文串。

例如串 babcbabcbaccba 最长回文是:abcbabcba

这个题目小弟给出3中解法，前两种的都是 O(n^2)， 第三种思路是O(n). 

思路1. 动态规划

这里动态规划的思路是 dp[i][j] 表示的是 从i 到 j 的字串，是否是回文串。

则根据回文的规则我们可以知道：

如果s[i] == s[j] 那么是否是回文决定于 dp[i+1][ j - 1]

当 s[i] != s[j] 的时候， dp[i][j] 直接就是 false。

动态规划的进行是按照字符串的长度从1 到 n推进的。

代码很明晰：给出java代码，复杂度 O(n^2)

T = # a # b # a # a # b # a #P = 0 1 0 3 0 1 6 1 0 3 0 1 0

例如上面的例子，最长回文是 “abaaba”, P_{6 = 6.}

根据观察发现，如果我们在一个位置例如 abaaba的中间位置，用一个竖线分开，两侧的P值是对称的。当然这个性质不是在任何时候都会成立，接下来就是分析如何利用这个性质，使得我们可以少算很多P的值。

下面的例子 S = “babcbabcbaccba” 存在更多的折叠回文字串。

C表示当前的回文中心，L和R处的线表示以C为中心可以到达的最左和最右位置，如果知道这些，我们如何可以更好的计算C后面的P[i]. 假设我们当前计算的是 i = 13, 根据对称性，我们知道对称的那个下标 i' = 9. 
根据C对称的原则，我们很容易得到如下数据 P[ 12 ] = P[ 10 ] = 0, P[ 13 ] = P[ 9 ] = 1, P[ 14 ] = P[ 8 ] = 0).
Now we are at index i = 15, and its mirrored index around C is i’ = 7. Is P[ 15 ] = P[ 7 ] = 7?

当时当i = 15的时候，却只能得到回文 “a#b#c#b#a”, 长度是5， 而对称 i ' = 7 的长度是7. 

如上图所示，如果以 i, i' 为中心，画出对称的区域如图，其中以i‘ = 7 对称的区域是 实心绿色 + 虚绿色 和 左侧，虚绿色表示当前的对称长度已经超过之前的对称中心C。而之前的P对称性质成立的原因是 i 右侧剩余的长度 R - i 正好比 以 i‘ 为中心的回文小。 这个性质可以这样归纳，对于 i 而言，因为根据C对称的最右是R，所以i的右侧有 R - i 个元素是保证是 i' 左侧是对称的。 而对于 i' 而言他的P值，也就是回文串的长度，可能会比 R-i 要大。 如果大于 R - i, 对于i而言，我们只能暂时的先填写 P[i] = R - i, 然后依据回文的属性来扩充P[i] 的值； 如果P[i '] 小于R-i，那么说明在对称区间C内，i的回文串长度和i' 是一样长的。例如我们的例子中 i = 15, 因为R = 20，所以i右侧 在对称区间剩余的是 R - 15 = 5, 而 i’ = 7 的长度是7. 说明 i' 的回文长度已经超出对称区间。我们只能使得P[i] 赋值为5， 然后尝试扩充P[i]. if P[ i' ] ≤ R – i,
then P[ i ] ← P[ i' ]
else P[ i ] ≥R – i. (这里下一步操作是扩充 P[ i ].

扩充P[i] 之后，我们还要做一件事情是更新 R 和 C， 如果当前对称中心的最右延伸大于R，我们就更新C和R。在迭代的过程中，我们试探i的时候，如果P[i'] <= R - i, 那么只要做一件事情。 如果不成立我们对当前P[i] 做扩展，因为最大长度是n，扩展最多就做n次，所以最多做2*n。 所以最后算法复杂度是 O(n)

或许贴上代码更容易一些。直接使用大神的代码了，虽然自己也实现了，不过是理解大神的思路实现的。

// Transform S into T.// For example, S = "abba", T = "^#a#b#b#a#$".// ^ and $ signs are sentinels appended to each end to avoid bounds checkingstring preProcess(string s) {  int n = s.length();  if (n == 0) return "^$";  string ret = "^";  for (int i = 0; i < n; i++)    ret += "#" + s.substr(i, 1);   ret += "#$";  return ret;} string longestPalindrome(string s) {  string T = preProcess(s);  int n = T.length();  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;   return s.substr((centerIndex - 1 - maxLen)/2, maxLen);}

查看更多 下一篇