求解一个字符串的最长回文子串
最朴素的想法是以每个点为中心向两边扩，看能扩多远，另外还需注意回文串长度为偶数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的那一刻很开心，继续加油！
