总结最长回文子串的几种做法 Longest Palindrome Substring，longestpalindrome

总结最长回文子串的几种做法 Longest Palindrome Substring，longestpalindrome

题目是：找出一个字符串中的最长回文子串。

例如：abcbcbb 的最长回文子串是 bcbcb

首先一种常见的错误方法是把原字符串S倒转过来成为S‘，以为这样就将问题转化成为了求S和S’的最长公共子串的问题。反例S="abacdfgdcaba"，若按这种解法得到答案是："abacd"，显然不是回文，而正确答案是"aba"

PS：这也是LeetCode的一道题：http://blog.csdn.net/fightforyourdream/article/details/15025663

下面总结一下四种解法：(面试时推荐中心展开法)

1）暴力法:Time:O(n^3), Space:O(1)

2）DP法：Time:O(n^2), Space:O(n^2)

http://faculty.utpa.edu/liuy2/algorithmGroup.html

3）中心展开法：Time:O(n^2), Space:O(n)  ***推荐面试时用！！！

http://blog.163.com/zhaohai_1988/blog/static/2095100852012716105847112/

4）Manacher算法：Time:O(n)，Space: O(n)   （精妙但较麻烦）

http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

下面是实现代码：

package String;

public class LongestPalindromeSubstring {

	
	// 暴力法 Time Complexity: O(n^3)
	public static String longestPalindromeBruteForce(String s) {
		String longest = "";
		if(s.isEmpty()) {
			return longest;
		}
		
		for(int i=0; i<s.length(); i++) {		// 开始位置
			for(int j=i; j<s.length(); j++) {	// 结束位置
				String substr = s.substring(i, j+1);
				if(j-i+1 > longest.length() && isPalindrome(substr)) {
					longest = substr;
				}
			}
		}
		return longest;
	}
	
	// O(n) 检查是否为回文
	private static boolean isPalindrome(String s) {
		int len = s.length();
		for(int i=0; i<=len/2; i++) {
			if(s.charAt(i) != s.charAt(len-1-i)) {
				return false;
			}
		}
		return true;
	}
	
	// ===========================================
	// 动态规划1 时间复杂度O(N2), 空间复杂度O(N2)
	public static String longestPalindromeDP1(String s) {
		int len = s.length();
		int longestBegin = 0;
		int maxLen = 1;
		boolean[][] isPalindrome = new boolean[len+1][len+1];
		
		for(int i=0; i<len; i++) {
			isPalindrome[i][i] = true;
		}
		
		for(int i=0; i<len-1; i++) {
			if(s.charAt(i) == s.charAt(i+1)) {
				isPalindrome[i][i+1] = true;
				longestBegin = i;
				maxLen = 2;
			}
		}
		
		for(int l=2; l<=len; l++) {			// 回文子串的长度
			for(int i=0; i<len-l+1; i++) {	// 回文子串的开始位置
				int j = i+l-1;					// 回文子串的结束位置
				if(isPalindrome[i+1][j-1] && s.charAt(i) == s.charAt(j)) {
					isPalindrome[i][j] = true;
					longestBegin = i;
					maxLen = l;
				}
			}
		}
		
		return s.substring(longestBegin, longestBegin+maxLen);
	}
	
	
	// ===========================================
	// 中心展开法 时间复杂度O(N2), 空间复杂度O(1)
	public static String longestPalindromeExpand(String s) {
		int len = s.length();
		if(len == 0) {
			return "";
		}
		String longest = s.substring(0, 1);
		for(int i=0; i<len; i++) {
			// 当回文为奇数长度时
			String p1 = 	expandAroundCenter(s, i, i);
			if(p1.length() > longest.length()) {
				longest = p1;
			}
			// 当回文为偶数长度时
			String p2 = expandAroundCenter(s, i, i+1);
			if(p2.length() > longest.length()) {
				longest = p2;
			}
		}
		return longest;
	}
	
	// c1, c2为展开的中心位置
	private static String expandAroundCenter(String s, int c1, int c2) {
		int l = c1, r = c2;
		int len = s.length();
		// 如果检查位置相等，则分别往左右展开
		while(l>=0 && r<=len-1 && s.charAt(l)==s.charAt(r)) {
			l--;
			r++;
		}
		return s.substring(l+1, r);		// 回文子串
	}
	
	
	// ===========================================
	// Manacher算法, Time: O(N), Space: O(N)
	// http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
	public static String longestPalindromeManacher(String s) {
		String T = preProcess(s);
		int len = T.length();			// 经过变化后，len总是为奇数长
		int[] P = new int[len];		// P数组存放在某index下的回文半径长度
		int C = 0, R = 0;		// C为最长回文子串的中心位置，R为当前最长回文子串的右边界位置
		for(int i=1; i<len-1; i++) {
			int iMirror = C - (i-C);	// 计算i的对应回文左边匹配位置i' 
			
			/*
			 if (R - i > P[iMirror]) 
			    P[i] = P[iMirror];
			else 				  // P[iMirror] >= R - i
			    P[i] = R - i;   // P[i] >= R - i，取最小值，之后再匹配更新。
			
			可简写成P[i] = (R > i) ? Math.min(R-i, P[iMirror]) : 0;
			 */
			P[i] = (R > i) ? Math.min(R-i, P[iMirror]) : 0;
			
			// 贪心拓展以i为回文中心的回文子串
			while(T.charAt(i+1+P[i]) == T.charAt(i-1-P[i])) {
				P[i]++;
			}
			
			// 如果以i为中心的回文扩展超过了R，则我们找到一个新的更长回文子串
			// 因此 更新 最长回文子串的中心和右边界
			if(P[i] > R-i) {
				C = i;
				R = i + P[i];
			}
		}
		
		// 现在P[i]数组里存放了以i为中心的回文子串长度，用打擂台方式找到最长者
		int maxLen = 0;
		int centerIndex = 0;
		for(int i=1; i<len-1; i++) {
			if(P[i] > maxLen) {
				maxLen = P[i];
				centerIndex = i;
			}
		}
		
		int start = (centerIndex-1-maxLen)/2;
		int end = start + maxLen;
		return s.substring(start, end);
	}
	
	// 把s转换成T，如s="abba"，则T="^#a#b#b#a#$"
	// ^和$加在字符串首尾用来避免边界检查
	private static String preProcess(String s) {
		int len = s.length();
		if(len == 0) {
			return "^$";
		}
		String ret = "^";
		for(int i=0; i<len; i++) {
			ret += "#" + s.substring(i, i+1);
		}
		ret += "#$";
		return ret;
	}
	
	
	public static void main(String[] args) {
//		String s = "abacdfgdcaba";
		String s = "abcbcbb";
		System.out.println(longestPalindromeBruteForce(s));
		System.out.println(longestPalindromeDP1(s));
		System.out.println(longestPalindromeExpand(s));
		System.out.println(longestPalindromeManacher(s));
	}

}

最后:

这道题其实还可以用后缀树(Suffix Tree)来做，但是复杂度（O(nlogn)）超过Manacher算法，并且实现起来更加麻烦，所以暂时没添加进来。