Contents

1. 1. 暴力 O(n^3)
2. 2. 枚举中心对称点
3. 3. Manacher’s ALGORITHM算法

• leetCode 005

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.

• 题意：

求一个字符串中的最长回文子串。

暴力 O(n^3)

枚举中心对称点

• O(n^2)

//给每个字符串都找一个中心对称点,然后从中心对称点向两边扩散找最大长度的子串
//预处理，使每个字符串都有一个中心对称点，例如：abcba -> #a#b#c#b#a#    abba  -> #a#b#b#a#
public String preProcess(String s) {
    if(s.length() == 0)
        return "#";
    String result = "";
    for(int i = 0; i < s.length(); i++) {
        result += "#" + s.charAt(i);
    }
    result += "#";
    return result;
}

public String longestPalindrome(String s) {

	if(s.length() == 1){
		return s;
	}
	
	s = preProcess(s);
	
    int maxs = 1, L = 0, R = 0;
    //枚举中心对称点
    for(int i = 0; i < s.length(); i++){
        int left = i - 1;
        int right = i + 1;
        int len = 1;
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            len += 2;
            
            if(len > maxs){
                maxs = len;
                L = left;//记录最长的回文串的边界
                R = right;
            }
            left--;
            right++;
        }
    }

    StringBuilder sb = new StringBuilder();
    for(int i = L; i < R; i++){
        if(s.charAt(i) != '#')
            sb.append(s.charAt(i));
    }
    return sb.toString();
}

Manacher’s ALGORITHM算法

参考：
http://blog.csdn.net/insistgogo/article/details/12287805

//预处理，使每个字符串都有一个中心对称点,且增加头标记和尾标记，这样在从中点向两边扩散的时候就不需要另外判断边界了
//例如：abcba -> $#a#b#c#b#a#_    abba  -> $#a#b#b#a#_
public String preProcess(String s) {
    if(s.length() == 0)
        return "#";
    StringBuilder result = new StringBuilder("$");  //加一个头标记

    for(int i = 0; i < s.length(); i++) {
        result.append('#');  
        result.append(s.charAt(i));
    }
    result.append("#_");  //加一个尾标记_

    return result.toString();
}

public String longestPalindrome(String s) {  
	
    String t = preProcess(s);
    int n = t.length();
    //p数组记录以该节点为中心对称点的最长回文子串的半径
    int[] p = new int[n];

    // mx为当前存在的回文子串能达到最右的位置+1
    //id为当前能到达最右+1的回文子串的回文中心点位置
    //maxs记录p数组中最大值  
    //m_mid记录最长子回文串的中点
    int mx = 0, id = 0, maxs = 0;  
    int m_mid = 0;  
    for (int i = 1; i < t.length() - 1; i++) {  
    	//最重要的是下面这句
        p[i] = mx > i ? Math.min(p[2 * id - i], mx - i) : 1;  

        while (t.charAt(i + p[i]) == t.charAt(i - p[i]))  
            p[i]++;  
        if (i + p[i] > mx) {  
            mx = i + p[i];  
            id = i;  
        }  
        if (maxs < p[i]) {  
            maxs = p[i];  
            m_mid = i;  
        }  
    }  
    // 最长为maxs - 1  
    return s.substring(m_mid/2 - maxs/2, m_mid/2 - maxs/2 + maxs-1);  
}