leetcode-5.最長回文子串-manacher

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

leetcode-5

該題使用馬拉車算法解時間複雜度和空間複雜度均為 O ( n ) O(n) O(n)

manacher思想介紹：

一、(center) C C C為回文串對稱中心坐标

二、(radius) R [ C ] R [C] R[C] 以C為對稱中心的回文串半徑

三、(iterator) I I I 對稱中心在R[C]範圍内，且 I > C I>C I>C的回文串對稱中心坐标

四、(Point) P P P以C為中心，回文串結束的下标

下面假設有一個字元串， i ‘ 為 i 的 對 稱 點 i`為i的對稱點 i‘為i的對稱點

此時 R [ i ] 有 兩 種 情 況 ， R [ i ] ≤ P 或 R [ i ] > P R[i]有兩種情況，R[i] \le P 或 R[i] \gt P R[i]有兩種情況，R[i]≤P或R[i]>P

情況一： 由于 i ‘ i` i‘是已經周遊過的位置，是以存在 R [ i ‘ ] > 0 & & R [ i ‘ ] = = R [ i ] R[i`] \gt0 \&\&R[i`] == R[i] R[i‘]>0&&R[i‘]==R[i] ，但此時p點之後的情況是未知的，故将R[i]指派為 m i n ( R [ i ‘ ] , P − i ) min(R[i`],P-i) min(R[i‘],P−i),為的是保證 i + R [ i ] ≤ P i + R[i] \le P i+R[i]≤P

情況二： 由于 i + R [ i ] > P i + R[i] \gt P i+R[i]>P, 故将 C C C點狀态轉移到 i i i點。

分析完馬拉車的兩種情況之後可以得出代碼套路：

1. 将字元串進行處理，友善統計
2. 對字元串進行周遊，利用對稱關系和輔助數組，周遊一遍即可得到最長回文子串的對稱中心所在。
3. 然後将答案處理至答案數組。

STEP1： 由于字元串長度分奇偶，首先将字元串處理，在字元串中加入一個沒有的字元， 如 ‘#’，處理後的字元串性質無改變，隻是将奇偶情況合并為一種情況，得到輔助字元串。如 ：

原字元串回文串為==偶數== abbad -> #a#b#b#a#d#    此時原字元串的對稱中心由bb之間轉換為#，
原字元串回味串為==奇數== abad   -> #a#b#a#d#        此時對稱中心還是b
           

STEP2： 根據兩種情況對字元串進行周遊得到輔助數組 R R R

STEP3： 周遊輔助字元串，根據輔助數組求得最長的字元串；

class Solution {
public:     //馬拉車算法
    string getnewstring(string str) {
        string news = "#";
        for (int i = 0; i < str.size(); i++) {
            news += str[i];
            news += '#';
        }
        return news;
    }
    string longestPalindrome(string s) {
        string ns = getnewstring(s);
        int *r = new int[ns.size()], c;      
        r[0] = 1, c= 0;
        for (int i = 0; i < ns.size(); i++) {
            if (i >= c + r[c]) {
                r[i] = 1;
            } else {
                r[i] = min(r[2 * c - i], c + r[c] - i);
            }
            while (i - r[i] >= 0 && ns[i - r[i]] == ns[i + r[i]]) {
                r[i]++;
            }
            if (c + r[c] < i + r[i]) c = i;
        }
        int ans = 0; 
        string S = "";
        for (int i = 0; i < ns.size(); i++) {
            if (r[i]  <= ans) continue;
            ans = r[i];
            S = "";
            for (int j = i - r[i] + 1; j < i + r[i]; j++) {
                if (ns[j] == '#') continue;
                S += ns[j];
            }
        }
        return S;
    }
};