最长的回文子串

//中心拓展法
public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String longestPalindrome (String s) {
        // write code here
        if(s==null || s.length()==0) return s;
        int index=0;
        int max=0;
        for(int i=0;i<s.length();i++){
            if(max<maxLengthOfPalindrome(s,i,i)){
                index=i;
                max=maxLengthOfPalindrome(s,i,i);
            }
            if(max<maxLengthOfPalindrome(s,i,i+1)){
                index=i;
                max=maxLengthOfPalindrome(s,i,i+1);
            }
        }
        if(max%2==1) return s.substring(index-max/2,index-max/2+max);
        else return s.substring(index+1-max/2,index+1+max/2);
    }
    private int maxLengthOfPalindrome(String s, int i, int j){
        int res=(i==j)?-1:0;
        while(i>=0 && j<s.length()){
            if(s.charAt(i)==s.charAt(j)){
                res+=2;
                i--;
                j++;
            }else{
                break;
            }
        }
        return res;
    }
}

public class Solution {
    public String longestPalindrome(String s) {
        if(s.length() <= 1)
            return s;
        int left = 0;int right = 0;
        int len = s.length();
        int max_len = 0;
        int length = 0;
        String res = "";
        for(int i = 0; i < len; i++){
            //类似cabac情况，回文字符串长度为奇数
            left  = right = i;
            while(left >= 0 && right < len && s.charAt(left) == s.charAt(right)){
                left --;
                right ++;
            }
            left++;right--;
            length = right - left + 1;
            if(length > max_len){
                max_len = length;
                res = s.substring(left , right + 1);
            }
            if(right == len -1)
                break;
            
            //类似abba情况，回文字符串长度为偶数
            left  = i;
            right = i + 1;
            while(left >= 0 && right < len && s.charAt(left) == s.charAt(right)){
                left --;
                right ++;
            }
            left++;right--;
            length = right - left + 1;
            if(length > max_len){
                max_len = length;
                res = s.substring(left , right + 1);
            }
            if(right == len -1)
                break;
        }
        return res;
    }
}

class Solution {
    int left=0,maxLen=0;
    public String longestPalindrome(String s) {
        if(s==null || s.length()<2)
            return s;
        for(int i=0;i<s.length();i++){
            findMaxPalindrome(s,i,i);
            findMaxPalindrome(s,i,i+1);
        }
        return s.substring(left,left+maxLen);
    }
    public void findMaxPalindrome(String s,int i,int j){
        while(i>=0 && j<s.length() && s.charAt(i)==s.charAt(j)){
            i--;
            j++;
        }
        if(maxLen<j-i-1){
            left = i +1;
            maxLen = j-i-1;
        }
    }
}

这题的我用的思路是动态规划：P[i][j]是记录i到j子串是不是回文串

P(i,j)={true,false,if the substring Si…Sj is a palindrome 则为true,否则为false
那么可以得到：  P(i,j)=(P(i+1,j−1) && Si==Sj)  。

public class Solution {
    private static boolean[][] dp;
    
    public String longestPalindrome(String s) {   

        int len = s.length();

        if (s == null || len == 0) return "";

        dp = new boolean[len][len];
        int i, j;

        //初始化dp数组
        for (i = 0; i < len; i++) {
            for (j = 0; j < len; j++) {
                //当i == j 的时候，只有一个字符的字符串; 当 i > j 认为是空串，也是回文,其他情况都初始化成不是回文
                dp[i][j] = i >= j ? true : false;
            }
        }

        int k, maxLen = 1;
        int rf = 0, rt = 0;

        for (k = 1; k < len; k++) {
            for (i = 0; i + k < len; i++) {
                j = i + k;
                //对字符串 s[i....j] 如果 s[i] != s[j] 那么不是回文
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else { //如果s[i] == s[j] 回文性质由 s[i+1][j-1] 决定
                    dp[i][j] = dp[i + 1][j - 1];
                    if (dp[i][j]) {
                        if (k + 1 > maxLen) {
                            maxLen = k + 1;
                            rf = i;
                            rt = j;
                        }
                    }
                }
            }
        }

        return s.substring(rf, rt + 1);

    }
}

// manacher算法 On
import java.util.*;
public class Solution {
    public String process(String str){
        String res="#";
        for(char c:str.toCharArray())
            res+=(c+"#");
        return res;
    }
    public String longestPalindrome(String s) {
        String str=process(s);
        int maxright=0, pos=0;
        int maxstart=0, maxl=0;
        int n=str.length();
        int[] mr=new int[n];
        for(int i=0;i<n;i++){
            if(i<maxright){
                mr[i]=Math.min(maxright-i,mr[2*pos-i]);
            }
            else
                mr[i]=1;
            while(i+mr[i]<n&&i-mr[i]>=0&&str.charAt(i+mr[i])==str.charAt(i-mr[i])){
                mr[i]++;
            }
            if(i+mr[i]-1>maxright){
                maxright=i+mr[i]-1;
                pos=i;
            }
            if(mr[i]>maxl){
                maxl=mr[i];
                maxstart=i-mr[i]+1;
            }
        }
        return s.substring(maxstart/2,maxstart/2+maxl-1);
    }
}

The performance is pretty good, surprisingly.

public class Solution { private int lo, maxLen; public String longestPalindrome(String s) { int len = s.length(); if (len < 2) return s; for (int i = 0; i < len-1; i++) {
     	extendPalindrome(s, i, i); //assume odd length, try to extend Palindrome as possible extendPalindrome(s, i, i+1); //assume even length. } return s.substring(lo, lo + maxLen);
} private void extendPalindrome(String s, int j, int k) { while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
		j--;
		k++;
	} if (maxLen < k - j - 1) {
		lo = j + 1;
		maxLen = k - j - 1;
	}
}}