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

最朴素的想法是以每个点为中心向两边扩，看能扩多远，另外还需注意回文串长度为偶数1221时的问题。复杂度O(n^2),这里不再详细介绍，直接上代码

public class Solution {
    private int lo;
    private int max;
    public String longestPalindrome(String s) {
        if(s.length()<2)
            return s;
        for(int i=0;i<s.length()-1;i++){
            longestPalHelper(s,i,i);
            longestPalHelper(s,i,i+1);
        }
        return s.substring(lo,max+lo);
    }
    public void longestPalHelper(String s,int i,int j){
        while(i>=0 && j<s.length()&&s.charAt(i)==s.charAt(j)){
            i--;
            j++;
        }
        if(j-i-1>max){
            max=j-i-1;
            lo=i+1;
        }
    }
}

一个特殊处理技巧，先把原来的字符串扩大1221变为#1 #2#2#1#，这样就避免了分出情况讨论回文串长度为偶数，121 #1#2#1#，利用求得的长度除以2就是原来回文串的长度。(加上啥都行，不一定是# 例如上例可以是1也可以是2)
加上#之后的字符串为处理串，现在对处理串进行处理，具体过程如图片所示。

man.jpg

求回文串长度的代码

public static int longestPalindrome(String s) {
        StringBuilder sb=new StringBuilder();
        sb.append("#");
        for(int i=0;i<s.length();i++){
            sb.append(s.charAt(i));
            sb.append("#");
        }
        String newString=sb.toString();
        int[] PArr=new int[newString.length()];
        int PR=0;
        int index=0;
        int max=0;
        for(int i=0;i<PArr.length;i++){
            if(i<PR){
                int i1=2*index-i;
                int smallR=PArr[i1];
                int leftSmall=i1-smallR+1;
                int leftBig=index-PArr[index]+1;
                if(leftSmall>leftBig)
                    PArr[i]=smallR;
                else if(leftSmall<leftBig){
                    PArr[i]=PR-i;
                }
                else{
                    int r=smallR;
                    while(i-r>=0&&i+r<PArr.length&&newString.charAt(i-r)==newString.charAt(i+r)){
                        r++;
                    }
                    PArr[i]=r;
                    PR=i+r;
                    index=i;
                }
            }
            else{
                int r=1;
                while(i-r>=0&&i+r<PArr.length&&newString.charAt(i-r)==newString.charAt(i+r)){
                    r++;
                }
                PArr[i]=r;
                PR=i+r;
                index=i;
            }
            max=Math.max(max,PArr[i]);
        }
        return max-1;
    }

求最长回文子串
[leetcode5]https://leetcode.com/problems/longest-palindromic-substring/
使用Manacher算法

public class Solution {
     public String longestPalindrome(String s) {
        StringBuilder sb=new StringBuilder();
        sb.append("#");
        for(int i=0;i<s.length();i++){
            sb.append(s.charAt(i));
            sb.append("#");
        }
        String newString=sb.toString();
        int[] PArr=new int[newString.length()];
        int PR=0;
        int index=0;
        int max=0;
        int maxIndex=0;
        for(int i=0;i<PArr.length;i++){
            if(i<PR){
                int i1=2*index-i;
                int smallR=PArr[i1];
                int leftSmall=i1-smallR+1;
                int leftBig=index-PArr[index]+1;
                if(leftSmall>leftBig)
                    PArr[i]=smallR;
                else if(leftSmall<leftBig){
                    PArr[i]=PR-i;
                }
                else{
                    int r=smallR;
                    while(i-r>=0&&i+r<PArr.length&&newString.charAt(i-r)==newString.charAt(i+r)){
                        r++;
                    }
                    PArr[i]=r;
                    PR=i+r;
                    index=i;
                }
            }
            else{
                int r=1;
                while(i-r>=0&&i+r<PArr.length&&newString.charAt(i-r)==newString.charAt(i+r)){
                    r++;
                }
                PArr[i]=r;
                PR=i+r;
                index=i;
            }
            if(PArr[i]>max){
                max=PArr[i];
                maxIndex=index;
            }
        }
        StringBuilder stringBuilder=new StringBuilder();
        int begin=maxIndex-max+1;
        int end=maxIndex+max-1;
        for(int i=begin+1;i<=end;i+=2){
            stringBuilder.append(newString.charAt(i));
        }
        return stringBuilder.toString();
    }
}

从学习Manacher算法到现在把代码实现，用了整整一晚上的时间，leetcode上accept的那一刻很开心，继续加油！