一墩划、題目

給定一個字符串 s涕刚，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000乙帮。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案杜漠。
示例 2：
輸入: "cbbd"
輸出: "bb"

二、解題

首先用一個非常巧妙的方式察净，將所有可能的奇數(shù)/偶數(shù)長度的回文子串都轉(zhuǎn)換成了奇數(shù)長度：在每個字符的兩邊都插入一個特殊的符號驾茴。比如 abba 變成 #a#b#b#a#， aba變成 #a#b#a#氢卡。 為了進(jìn)一步減少編碼的復(fù)雜度锈至，可以在字符串的開始加入另一個特殊字符，這樣就不用特殊處理越界問題异吻，比如$#a#b#a#（注意裹赴，下面的代碼是用C語言寫就喜庞，由于C語言規(guī)范還要求字符串末尾有一個'\0'所以正好OK诀浪，但其他語言可能會導(dǎo)致越界）。

下面以字符串12212321為例延都，經(jīng)過上一步雷猪，變成了 S[] = "$#1#2#2#1#2#3#2#1#";

然后用一個數(shù)組 P[i] 來記錄以字符S[i]為中心的最長回文子串向左/右擴(kuò)張的長度（包括S[i]，也就是把該回文串“對折”以后的長度）晰房，比如S和P的對應(yīng)關(guān)系：

S  #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #
P  1  2  1  2  5  2  1  4  1  2  1  6  1  2  1  2  1
(p.s. 可以看出求摇，P[i]-1正好是原字符串中回文串的總長度）

那么怎么計算P[i]呢？該算法增加兩個輔助變量（其實(shí)一個就夠了殊者，兩個更清晰）id和mx与境，其中 id 為已知的 {右邊界最大} 的回文子串的中心，mx則為id+P[id]猖吴，也就是這個子串的右邊界摔刁。

然后可以得到一個非常神奇的結(jié)論，這個算法的關(guān)鍵點(diǎn)就在這里了：如果mx > i海蔽，那么P[i] >= MIN(P[2 * id - i], mx - i)共屈。就是這個串卡了我非常久。實(shí)際上如果把它寫得復(fù)雜一點(diǎn)党窜，理解起來會簡單很多：

//記j = 2 * id - i拗引，也就是說 j 是 i 關(guān)于 id 的對稱點(diǎn)(j = id - (i - id))
if (mx - i > P[j]) 
    P[i] = P[j];
else /* P[j] >= mx - i */
    P[i] = mx - i; // P[i] >= mx - i，取最小值幌衣，之后再匹配更新矾削。

當(dāng)然光看代碼還是不夠清晰，還是借助圖來理解比較容易。

當(dāng) mx - i > P[j] 的時候哼凯，以S[j]為中心的回文子串包含在以S[id]為中心的回文子串中垦细，由于 i 和 j 對稱，以S[i]為中心的回文子串必然包含在以S[id]為中心的回文子串中挡逼，所以必有 P[i] = P[j]括改，見下圖。

image.png

當(dāng) P[j] >= mx - i 的時候家坎，以S[j]為中心的回文子串不一定完全包含于以S[id]為中心的回文子串中嘱能，但是基于對稱性可知，下圖中兩個綠框所包圍的部分是相同的虱疏，也就是說以S[i]為中心的回文子串惹骂，其向右至少會擴(kuò)張到mx的位置，也就是說 P[i] >= mx - i做瞪。至于mx之后的部分是否對稱对粪，就只能老老實(shí)實(shí)去匹配了。

image.png

對于 mx <= i 的情況装蓬，無法對 P[i]做更多的假設(shè)著拭，只能P[i] = 1，然后再去匹配了牍帚。

于是代碼如下：

//輸入儡遮，并處理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
    p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    if (i + p[i] > mx) {
        mx = i + p[i];
        id = i;
    }
}
//找出p[i]中最大的

三、代碼示例

     class Solution {
        func longestPalindrome(_ s: String) -> String {
            if s.count <= 1 {
                return s
            }
            
            // 1.間隔之間先插入#
            var S = ["#"]
            for character in s {
                S.append(String(character))
                S.append("#")
            }
            
            // 2.遍歷找出以每個節(jié)點(diǎn)作為軸最長半徑
            var maxId:Int = 0
            var max:Int = 0
            var P:[Int] = [1]
            var maxLength:Int = 1
            var maxLengthIndex = 0
            
            for i in 1...S.count - 1 {
                // j是相對于maxId的i的左邊的對稱點(diǎn)
                let j:Int = maxId - (i - maxId)
                
                if max > i && j >= 0 {
                    // 優(yōu)化部分,請見文章
                    P.append(min(P[j], max - i))
                }else{
                    P.append(1)
                }
                // 循環(huán)判斷以i位置為中心的左右兩側(cè)是否相同,相同加1
                while i + P[i] <= S.count - 1 && i - P[i] >= 0 && S[i + P[i]] == S[i - P[i]]{
                    P[i] += 1
                }
                
                if i + P[i] - 1 > max {
                    // 以i為中心的子回文的最后一個元素的位置
                    max = i + P[i] - 1
                    // 記錄i為回文子串的中心id
                    maxId = i
                }
                
                // 判斷最長回文的長度,并記錄
                if P[i] > maxLength {
                    maxLength = P[i]
                    maxLengthIndex = i
                }
                print("i:\(i) maxId:\(maxId) max:\(max) maxLength:\(maxLength) maxLengthIndex:\(maxLengthIndex) P:\(P)")
            }
            let leftIndex = s.index(s.startIndex, offsetBy: (maxLengthIndex - (maxLength - 1))/2)
            let rightIndex = s.index(leftIndex, offsetBy:maxLength - 1 - 1)
            return String(s[leftIndex...rightIndex])
        }
    }

Demo地址：github
相關(guān)文章：Manacher's ALGORITHM: O(n)時間求字符串的最長回文子串