问题描述

给一个字符串，求其最长回文字串

样例

Input："babad"，Output："bab"，Note："aba" is also a valid answer。
Input："cbbd"，Output："bb"。

分析

解法一

可以使用暴力枚举法，将字符串的每一个字符作为中心点来扩散，定义两个游标left和right，枚举出每一种可能性，扩散的时候注意根据最长字串的奇偶性不同定义游标不同
该算法的时间复杂度为o(n^2)

java代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {

    public static void main(String[]args){
        System.out.println(getResult("abcdcbaccada"));
    }
    //暴力枚举法,时间复杂度为o(n^2)
    public static String getResult(String s){
        char[] A = s.toCharArray();
        int size=s.length();
        int length=0; //保存当前最长回文字串的长度
        int start=-1; //保存当前回文字串的起始位置
        for (int i=1;i<s.length()-2;i++){//由于回文字串既可能是偶数又可能是奇数长，所以偶数和奇数要同时判断
            //先判断回文字串为长度为奇数时
            int left=i-1;
            int right=i+1;
            while (left>=0&&right<size&&A[left]==A[right]){
                left--;
                right++;
            }
            if (right-left-1>length) {
                start=left+1;
                length=right-left-1;
            }
            //回文字串为偶数长度时
            left=i;
            right=i+1;
            while (left>=0&&right<size&&A[left]==A[right]){
                left--;
                right++;
            }
            if (right-left-1>length){
                start=left+1;
                length=right-left+1;
            }
        }
        return s.substring(start,length+start);
    }
}

解法二

Manacher 算法

使用该算法时间复杂度降为o(n)

预处理

为了避免讨论回文字串的奇偶问题，可以对对目标字符串进行预处理。
如s="ababcabcba",预处理为ss="#a#b#a#b#c#a#b#c#b#a",这样的话所有的回文字串全部转为奇数的情况

P数组

定义个P数组保存以s[i]为中心的最长回文半径，例如

image.png

那么p[i]-1就是最长回文字串的长度

核心算法

定义两个变量：mx、id

image.png

mx代表以s[id]为中心的最长回文右边界，即mx=id+p[id]

 if (i<mx) p[i]=Math.min(p[2*id-1-i],mx-i); //manacher核心算法
            else p[i]=1;
            while ((i-p[i])>=0&&(i+p[i])<newA.length&&newA[i-p[i]]==newA[i+p[i]]) p[i]++; //对应p[i]可能增加的情况

对上述代码进行讨论：
1.j的回文串又一部分在id外

image.png

那么p[i]=mx-i，如果p[i]超出此值，那么p[id]也超出原来值，这是不成立的

2.j的回文串全部在id内部

image.png

那么p[i]=p[j]，如果p[i]超出此值，那么p[j]也超出，不成立

3.j的回文串左端刚好是id的左边界

image.png

java代码

public static char[] preTreat(char[] A){
        char[] newA=new char[2*A.length+2];
        newA[0]='$';
        int j=1;
        for (int i=0;i<A.length;i++){
            newA[j++]='#';
            newA[j++]=A[i];
        }
        newA[j]='#';
        return newA;
    }
    public static int  Manacher(String s){
        char[] A=s.toCharArray();
        char[] newA=preTreat(A);
        int[] p=new int[newA.length];
        int id=1;
        int start=-1;
        int maxLength=1;
        int mx=0; //记录以id为中心的最长回文子序列的右边界
        //构建P数组：p[i]表示以i为中心的最长回文半径
        for (int i=1;i<newA.length;i++){
            if (i<mx) p[i]=Math.min(p[2*id-1-i],mx-i); //manacher核心算法
            else p[i]=1;
            while ((i-p[i])>=0&&(i+p[i])<newA.length&&newA[i-p[i]]==newA[i+p[i]]) p[i]++; //对应p[i]可能增加的情况
            if (mx<i+p[i]){ //保证mx尽量的远，提高效率
                id=i;
                mx=i+p[i];
            }
            maxLength=Math.max(maxLength,p[i]-1);
        }
        return maxLength;
    }

参考：https://segmentfault.com/a/1190000008484167