最長回文子串與馬拉車算法

最長回文子串

給你一個字元串 s，找到 s 中最長的回文子串。

示例 1：

輸入：s = "babad"

輸出："bab"

解釋："aba" 同樣是符合題意的答案。

1.中心擴充

尋找回文子串必須要找到子串并判斷他是否成中心對稱的，要麼檢查每一個子串，從兩側向中間周遊檢查對稱。要麼從中心向兩側邊檢查對稱邊取得子串。

第一種方法是暴力破解法，顯然更耗資源一些，是以可以采用第二種中心擴充法。

注意：要考慮串的對稱就要判斷一個串的字元數是奇數還是偶數。

設定一個mid周遊整個字元串

設定一個left/right由mid開始向左右擴充比較元素相同否，相同急需擴充

1.使用mid周遊串

2.需要進行中心為偶數的情況，如bb abba，是以left與right在最開始時，需要都判斷是否與mid相同，相同也進行移動

3.移動完後left/rigth開始左右擴充

4.每次擴充結束記錄長度，并比較是否是最大長度。

public String longestPalindrome(String s) {
int mid = 0;
int left = mid, right = mid;
int maxLen = 0, maxLeft = 0;
while(mid < s.length()){

while(left > 0 && s.charAt(left - 1) == s.charAt(mid)){
left--;
            }
while(right < s.length() - 1 && s.charAt(right + 1) == s.charAt(mid)){
right++;
            }
while(left > 0 && right < s.length() - 1 && s.charAt(left - 1) == s.charAt(right + 1)){
left--;
right++;
            }
if(maxLen < right - left + 1){
maxLen = right - left + 1;
maxLeft = left;

            }
mid++;
left = mid;
right = mid;
        }
return s.substring(maxLeft, maxLeft + maxLen);
    }
      

2.動态規劃

如果思考過中心擴充的邏輯可以知道，上一層子串是回文aa，這一層子串才可能也是回文baab。反之則不會是。也就是說目前狀态取決于上一層狀态，那麼這符合動态規劃的核心：狀态與狀态轉移。

1.确定dp數組與狀态：dp[i][j]代表從i開始到j的子串是否為回文子串

2.确定狀态轉移方程：

dp[i][j] = dp[i+1][j-1] && s[i]=s[j]

dp[i][j] = true && i=j

dp[i][j] = dp[i+1][i+1] && s[i]=s[j] && i+1=j

3.無邊界條件

4.若dp[i][j]為true考慮是否更新長度

class Solution {
public String longestPalindrome(String s) {   
boolean[][] dp = new boolean[s.length()][s.length()];
int maxLen = 0;
int begin = 0;
for(int i = 0; i < s.length(); i++){
for(int j = 0; j <= i; j++){
if(i == j){
dp[j][i] = true;
                }else{
if(s.charAt(j) == s.charAt(i)){
if(j + 1 == i){
dp[j][i] = true;
                        }else{
dp[j][i] = dp[j + 1][i - 1];
                        }
                    }else{
continue;
                    }
                }
if(dp[j][i]){
if(i - j + 1 > maxLen){
maxLen = i - j + 1;
begin = j;
                    }
                }
            }
        }
return s.substring(begin, begin + maxLen);
    }
}
      

3.Manacher(馬拉車)算法

馬拉車算法有點類似KMP算法的思想：對已經比較過的部分不在重複比較，以實作優化。

KMP算法利用比較過後的前字尾結構是相同的進行回溯，來優化對相同結構的比較。對于回文子串來說，馬拉車算法優化的是中心擴充方法，在中心擴充的時候，每個元素都要從中心出發向左右擴充。但是，在一個已經檢查完的回文子串中，其左側結構與右側結構是對稱的。若在左側結構中存在一個元素以他為中心存在回文子串，則右側結構中必然存在相應位置的元素以他為中心存在回文子串。我們通過對左側結構中回文子串長度的分析來獲得右側回文子串的最小長度來減少比較次數完成優化。

分析右側子串長度

1.我們認為已經檢查完的回文子串右側邊界為maxRigth。當我們有元素在其右側超過maxRight的位置出現時，我們無法在左側找到對應元素。是以隻能從該位置進行中心擴充。

2.若目前元素在maxRight内，我們找到在左側對應位置上的元素，再找到以其為中心的子串長度。若長度超過了其左側結構的邊界，那麼意味着我們無法在右側超過邊界的區域為目前元素找到檢查過的回文結構。是以我們設定目前元素的最小子串長度為maxRight到目前元素的距離，然後進行中心擴充。

3.若目前元素在maxRight内，且其中心子串長度小于左側結構邊界。這意味着我們右側結構中的中心子串和他是完全對稱的。那麼長度也是相同的，将目前元素長度設定為左側對應元素的中心子串長度。

算法準備

1.馬拉車的核心思想容易了解，但是代碼實作時的位置關系不好了解。首先我們為了規避奇數串和偶數串長度問題，需要在原串的元素間隔和串的兩端加上特殊符号，一般為“#”。這樣得到的新串必然為奇數串，友善尋找中心子串。

2.設定一個半徑的概念，半徑是中心子串由中心元素到左右兩端的元素個數。

3.設定中心指針指向子串中心元素。

4.設定一個目前已經檢查過的子串中，最右側元素的下标指針。

5.設定一個數字記錄每個元素的子串長度。

6.設定記錄最大串的中心元素指針和最大串的半徑。

算法實作

0.插入特殊符号建構新串

1.依次周遊串中元素。

2.執行分析右側子串長度的邏輯。

3.檢查目前獲得的子串邊界是否超過了目前最遠的最右側元素。若是，更新最右側元素下标，子串中心下标。

4.檢查目前獲得的子串半徑是否大于最大串的半徑。

5.周遊結束

6.按最優結果截取子串傳回結果。

剩餘問題

如何進行分析子串長度已經交代過了，那如何建構新串和根據新串傳回原串結果呢？

1.建構新串。分析#a#b#與#a#b#c#兩種情況可知，特殊符号的下标永遠是偶數。字元在原串中的位置要被特殊符号擠占，原串中前面有n個字元，新串前面就有n+1個特殊符号。是以周遊新串偶數為置‘#’，奇數位為目前下标/2取整得到的結果在原串中的元素。

2.傳回結果。現在我們有了最優的子串的半徑和中心下标，我們需要的是原串中的子串的起始位置下标和子串長度。

-起始位置：我們隻需要用中心位置下标減去其右側的元素個數就可以得到子串在新串的起始下标。右側元素個數可以由半徑-1得到（半徑是中心到兩端的元素個數，是以要減掉中心）。由于每一個元素之前都有一個特殊字元#。我們可以認為每一對"#字元"對應原串的一個元素。#a對應a,是以對下标0和1通過除2取整可以得到#a對應的原串下标0。是以，我們得到的子串在新串的起始下标除2取整就可以得到子串在原串的起始下标。

-長度：考慮#a#b#a#與#a#a#的半徑分别是4與3。其元素個數分别為3與2。是以半徑-1就是子串在原串中的元素個數。

代碼如下：

public String longestPalindrome(String s) {
if(s.length() <= 1){
return s;
        }
char[] newArray = new char[2 * s.length() + 1];
for(int i = 0; i< newArray.length; i++){
newArray[i] = i % 2 == 0 ? '#' : s.charAt(i / 2);
        }
int maxCenter = 0, maxRight = 0, resR = 0, resCenter = 0;
int[] maxR = new int[newArray.length];
for(int i = 0; i < newArray.length; i++){
if(i < maxRight){
if(maxR[2 * maxCenter - i] < maxRight - i){ 
maxR[i] = maxR[2 * maxCenter - i];
                }else{
maxR[i] = maxRight - i;
while(i + maxR[i] < newArray.length && i - maxR[i] >= 0 && newArray[i + maxR[i]] == newArray[i - maxR[i]]){
maxR[i]++;
                    }
                }
            }else{
maxR[i] = 1; //半徑包含自己，是以初值為1
while(i + maxR[i] < newArray.length && i - maxR[i] >= 0 && newArray[i + maxR[i]] == newArray[i - maxR[i]]){
maxR[i]++;
                    }
            }
if(i + maxR[i] > maxRight){
maxRight = i + maxR[i];
maxCenter = i;
            }
if(maxR[i] > resR){
resR = maxR[i];
resCenter = i;
            }
        }
resR -= 1;
int begin = (resCenter - resR) >> 1;
return s.substring(begin, begin + resR);
    }