馬拉車算法是用來查找回文串的線性方法。

回文串是什么呢？

回文串是一種正反讀都一樣的字符串，比如bob noon 等都是回文字符串
如何在一個字符串中找出最長回文子字符串呢？

在上一篇的動態(tài)規(guī)劃中就有這樣的方法
當時是這樣做的,創(chuàng)建一個boolean dp數組，表示從i 到 j的字符串是否回文
狀態(tài)轉義方程
如果 s[i] == s[j]
dp[i][j] == dp[i + 1][j - 1];
否則直接為false
初始狀態(tài)
dp[i][i] 直接為 true

dp[i][i+1]需要循環(huán)判斷值是否相等
隨后 i從末尾，j從頭部直接雙循環(huán)遍歷，即可得出結果

在馬拉車算法中 首先對字符串做預處理，防止對字符串的奇偶性進行討論，首先在字符串的首尾和每個字符之間加上#符號，這樣我們的字符串長度如果原來為n 現在變?yōu)?n+1 必然為奇數

然后我們如果找到了回文串，還要定位到回文串的長度和下標，這樣才能截取這個回文串
比如字符串bob
處理之后變?yōu)?#b#o#b#
那么處理之后，這個回文串的半徑為4，實際長度為3
回文串的長度為半徑-1
這個結論得出也很簡單，因為處理后回文串的長度為2n+1,那么半徑長度為n+1,原字符串長度為n，自然回文串的長度為新回文串半徑-1

光知道長度還不夠，現在必須知道這個字符串的在原來串中的起始位置

現在b在bob中的索引為0，那么如何定位到這個0呢
我們設bob字符串的長度為n處理后字符串的長度為2n+1,中心點o的位置為n，半徑為n+1

如果字符串為moom
處理后為#m#o#o#m#
m為moom的索引為0，處理后字符串為2n+1， 處理后半徑n+1 中心點位置還是n

我們發(fā)現中心點位置 + 1 減去半徑則為0，但是如果是其他字符串

ex 122122
處理后 #1#2#2#1#2#2#
如果其半徑為n，中心位置下標隨著前置元素的增加而往后移動

所以只能為中心位置 - 半徑，但是上述兩者均為-1
那么處理字符串的時候在前面加上一個不會被用到的特殊字符$
加上后，處理后字符串的中心下標+1，那么n + 1 - n -1 = 0，而且前面每加上一個非回文元素，中心下標會+2，原字符串只能+1,所以這里要除以2

那么原回文串起始下標為(處理后回文串中心位置 - 處理后回文串半徑)/2

這一行代碼是馬拉車算法核心點
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;

對i進行計算，mx為現有所有回文串的最右側
如果 mx > i
另 2* id - i = j 那么j為i關于id的對稱點，
如果j的半徑p[j] 在當前p[id]內部，那么 ij關于id堆成，那么p[i]也必然在mx內部，所以有p[i] = p[j]

image.png

如果j的半徑p[j] 超過mx對稱點，那么不知道m(xù)x對稱點左側和右側是否對稱，所以只能將值暫時設置為
mx - i 然后剩下的挨個計算

image.png

如果mx < i 也就是之前的回文右端都不超過mx，并且最右端的元素p[mx] = 1 時，只能定義p[i] = 1
對接下來的元素挨個計算；

代碼部分

public String malache(String s){
        //首先處理字符串
        String t = "$#";
        for (int i = 0; i < s.length(); i++){
            t += s.charAt(i);
            t += "#";
        }
        t += "~";
        //設置3個值
        int id = 0; //馬拉車算式中的id
        int returnLength = 0 ;// 最常子串的長度
        int returnIndex = 0;// 最長子串的起始索引
        int mx = 0;
        int [] p =  new int[t.length()];
        for (int i = 0; i < t.length(); i ++){
            // 馬拉車算法
            p[i] =mx > i ? Math.min(p[2 * id - i], mx - i):1;
            while (p[i] + i< t.length() && i - p[i] >=0 && t.charAt(i + p[i]) == t.charAt(i - p[i])){ //挨個計算值,邊界條件計算
                p[i] += 1;
            }

            if (mx < p[i] + i){ //刷新id
                mx = i + p[i];
                id = i;
            }
            if(returnLength < (p[i] - 1)){
                returnLength = p[i] - 1;
                returnIndex = (i - p[i])/2;
            }


        }
        return s.substring(returnIndex,returnIndex + returnLength);
    }