求解一個字符串的最長回文子串
最樸素的想法是以每個點為中心向兩邊擴荣暮，看能擴多遠奋姿，另外還需注意回文串長度為偶數(shù)1221時的問題。復(fù)雜度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變?yōu)?1 #2#2#1#口柳，這樣就避免了分出情況討論回文串長度為偶數(shù)竹勉，121 #1#2#1#剧包，利用求得的長度除以2就是原來回文串的長度。(加上啥都行滑燃，不一定是# 例如上例可以是1也可以是2)
加上#之后的字符串為處理串役听，現(xiàn)在對處理串進行處理，具體過程如圖片所示表窘。
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();
}
}
從學(xué)習Manacher算法到現(xiàn)在把代碼實現(xiàn)典予，用了整整一晚上的時間，leetcode上accept的那一刻很開心蚊丐，繼續(xù)加油熙参！
