问题描述
给一个字符串，求其最长回文字串
样例
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
此时：p[i]=p[j]=mx-i，并且可以p[i]可以继续扩展
while ((i-p[i])>=0&&(i+p[i])<newA.length&&newA[i-p[i]]==newA[i+p[i]]) p[i]++; //对应p[i]可能增加的情况
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;
}
网友评论