最长回文子串问题

在计算机科学中，最长回文子串或最长对称因子问题是在一个字符串中查找一个最长的连续的回文的子串，例如“banana”最长回文子串是“anana”。最长回文子串并不一定是唯一的，比如“abracadabra”，没有超过3的回文子串，但是有两个回文字串长度都是3：“ada”和“aca”。在一些应用中，我们求出全部的极大回文子串（不被其他回文串包含的回文子串）。

介绍Manacher于发现了一种线性时间算法，可以在列出给定字符串中从任意位置开始的所有回文子串。并且，Apostolico, Breslauer & Galil 发现，同样的算法也可以在任意位置查找全部极大回文子串，并且时间复杂度是线性的。因此，他们提供了一种时间复杂度为线性的最长回文子串解法。另外，Jeuring (1994), Gusfield (1997)发现了基于后缀树的算法。也存在已知的高效并行算法1。

最长回文子串算法不应当与最长回文子序列算法混淆。

例子1. 问题描述

回文串（palindromic string）是指这个字符串无论从左读还是从右读，所读的顺序是一样的；简而言之，回文串是左右对称的。所谓最长回文子串问题，是指对于一个给定的母串

abcdedcb2.穷举法

最容易想到的是穷举法，穷举所有子串，找出是回文串的子串，统计出最长的那一个。

// check whether a string is palindromicfunc isPalindromic(s string) bool { mid := len(s) / 2 last := len(s) - 1 for i := 0; i pR) { pR = i + pArr[i]; index = i; } max = Math.max(max, pArr[i]); } return max -1;}在字符串的最后添加最少字符, 使整个字符串都成为回文串, 其实就是查找在必须包含最后一个字符的情况下, 最长的回文串是什么。那么之前不是最长回文子串的部分逆序过来, 就是应该添加的部分。比如“abcd123321”,在必须包含最后一个字符的情况下,最长的回文子串是“123321”,之前不是最长回文子串的部分是“abcd”, 所以末尾应该添加的部分就是“dcba”。那么只要把manacher 算法稍作修改就可以。具体改为： 从左到右计算回文半径时, 关注回文半径最右即将到达的位置(pR),一旦发现已经到达最后(pR== charArr.length),说明必须包含最后一个字符的最长回文半径已经找到, 直接退出检查过程, 返回该添加的字符串即可。具体过程参看如下代码中的shortestEnd
方法。

public static String shortestEnd(String str) { if (str == null || str.length() == 0) { return null; }char[] charArr = manacherString(str); int[] pArr = new int[charArr.length]; int index=-1; int pR=-1; int maxContainsEnd = -1; for (int i = 0; i ! = charArr.length; i++) { pArr [i] = pR > i ? Math.min (pArr [2 *index - i], pR - i) : 1; while (i + pArr[i] -1) { if (charArr [i + pArr [i]] == charArr[i - pArr[i]]) pArr[i]++; else { break; } }if (i + pArr[i] > pR) {pR = i + pArr[i]; index = i; }if (pR == charArr.length) { maxContainsEnd = pArr[i]; break; } } char [] res = new char [str.length () -maxContainsEnd + 1]; for (int i = 0; i