LeetCode Problem：求字符串的最长回文子串

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.

 

这个题目是一个很常见的面试题，有暴力穷举法，最长前缀法，还有一个非常巧妙的方法，manacher's algorithm, 看到这个算法的时候，发现真的是太优美了，不得不佩服设计出这个算法的人。

本文参考了这篇文章：http://blog.csdn.net/ggggiqnypgjg/article/details/6645824

 

先假设

1) 数组为S,题目中的数组

2) 辅助数组T，T数组是在数组S的每个元素前后插入一个“#”，例如 

S = “caba”， 那么 T = "#c#a#b#a#"

S = "bb", 那么 T = “#b#b#”

3) 数组P，其中P[i] 表示以T[i] 为中心的回文串从T[i]到串边界的长度，有点拗口，看个例子， 例如

S=“bb”，那么T="#b#b#",

P[0] = 1  T[0] = "#" , 回文串为 “#"，#长度为1

P[1] = 2  T[1] = "b", 回文串为"#b#"，b#长度为2

P[2] = 3  T[2] = "#", 回文串为"#b#b#", #b#长度为3

4) id, mx, 其中 P[id] = mx, 表示最大回文串，那么这个串的起始索引是[id-mx+1], 终点索引是[id+mx-1]

例如3)里面，id = 2, mx = 3, 起始索引是id-mx+1 = 2-3+1=0,终点索引是id+mx-1=2+3-1=4

 

OK, 下面是程序(java实现)

	 public static String longestPalindrome(String s) {
	        if(s==null || s.length() == 0){
	            return "";
	        }
	        if(s.length() == 1){
	            return s;
	        }
	        String T = prePocess(s);
	        int i;
	        int mx = 0;
	        int id = 0;
	        int[] P = new int[T.length()];
	        for(i=1;i<T.length();i++){
	            if(mx > i){
	                P[i] = Math.min(P[2*id - i],mx-i);
	            }else{
	                P[i] = 1;
	            }
	            while((i+P[i]<T.length()) && (i-P[i])>=0 && T.charAt(i+P[i]) == T.charAt(i-P[i])){
	                P[i]++;
	            }
	            if(P[i]>mx){
	                mx = P[i];
	                id = i;
	            }
	        }
	        return T.substring(id-mx+1,id+mx-1).replace("#", "");  
	    }
	 
	 
	 public static String prePocess(String s){
		 StringBuffer sb = new StringBuffer();
		 for(int i=0;i<s.length();i++){
			 sb.append("#").append(s.charAt(i));
		 }
		 return sb.toString()+"#";
	 }

 

好了，让我们来看一下，最神奇的几行代码

 if(mx > i){

      P[i] = Math.min(P[2*id - i],mx-i);

 }else{

      P[i] = 1;

 }

 

看到 P[i] = Math.min(P[2*id - i],mx-i); 首先我心中有三个疑问：

1. P[i] 为什么比 mx - i 小？

2. P[i] 为什么比 P[2*id - i] 小？

3. P[i] 为什么取这二者的最小者？

 

其实是个折中，

首先，以i为中心，向右延伸mx-i长度的回文串肯定落在以id为中心，向右延伸mx长度的回文串里面。

我们只能在这个范围里面比较，因为超过id+mx的元素，还没有被比较过，所以限定这个范围，

那么在这个范围内，由于回文串的特点，以id为中心左右折叠是重合的，所以寻找i以id为中心的对称位置，

即2*id - i，而这个位置我们已经得到结果即P[2*id-i], 但是不能直接取P[2*id-i]， 因为P[2*id-i] 可能会大于mx-i，如果大于的话，那么就不在可控范围了，所以最后取二者最小值。

 

 

 

P.S:这个题目经常我面试阿里巴巴实习生的时候被面到过，当时不知道manacher's algorithm,所以只给了穷举算法，囧。