什么是Manacher(馬拉車)演算法-java代碼實作

截止到目前我已經寫了 500多道演算法題，其中部分已經整理成了pdf檔案，目前總共有1000多頁（并且還會不斷的增加），大家可以免費下載
下載鏈接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取碼：6666

之前在講《517，最長回文子串的3種解決方式》的時候，在最后提到過Manacher演算法，但是沒有寫，這里單獨拿出來寫，


我們來看個例子，比如字串"babad"在添加特殊字符之后每個字符的回文半徑

如果還看不明白，我們來隨便找個字串 “babcbabcbac” 畫個圖來看下

代碼如下，分三種情況判斷

    for (int i = 0; i < length; i++) {
        if (i < maxRight) {
            //情況一，i沒有超出范圍[left,maxRight]
            //2 * maxCenter - i其實就是j的位置，實際上是判斷p[j]<maxRight - i
            if (p[2 * maxCenter - i] < maxRight - i) {
                //j的回文半徑沒有超出范圍[left,maxRight]，直接讓p[i]=p[j]即可
                p[i] = p[2 * maxCenter - i];
            } else {
                //情況二，j的回文半徑已經超出了范圍[left,maxRight]，我們可以確定p[i]的最小值
                //是maxRight - i，至于到底有多大，后面還需要在計算
                p[i] = maxRight - i;
                //繼續計算
                while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]])
                    p[i]++;
            }
        } else {
            //情況三，i超出了范圍[left,maxRight]，就沒法利用之前的已知資料，而是要一個個判斷了
            p[i] = 1;
            //繼續計算
            while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]])
                p[i]++;
        }
    }

在來看下最終代碼

public String longestPalindrome(String s) {
    int charLen = s.length();//源字串的長度
    int length = charLen * 2 + 1;//添加特殊字符之后的長度
    char[] chars = s.toCharArray();//源字串的字符陣列
    char[] res = new char[length];//添加特殊字符的字符陣列
    int index = 0;
    //添加特殊字符
    for (int i = 0; i < res.length; i++) {
        res[i] = (i % 2) == 0 ? '#' : chars[index++];
    }

    //新建p陣列 ，p[i]表示以res[i]為中心的回文串半徑
    int[] p = new int[length];
    //maxRight(某個回文串延伸到的最右邊下標)
    //maxCenter(maxRight所屬回文串中心下標),
    //resCenter（記錄遍歷過的最大回文串中心下標）
    //resLen（記錄遍歷過的最大回文半徑）
    int maxRight = 0, maxCenter = 0, resCenter = 0, resLen = 0;
    //遍歷字符陣列res
    for (int i = 0; i < length; i++) {
        if (i < maxRight) {
            //情況一，i沒有超出范圍[left,maxRight]
            //2 * maxCenter - i其實就是j的位置，實際上是判斷p[j]<maxRight - i
            if (p[2 * maxCenter - i] < maxRight - i) {
                //j的回文半徑沒有超出范圍[left,maxRight]，直接讓p[i]=p[j]即可
                p[i] = p[2 * maxCenter - i];
            } else {
                //情況二，j的回文半徑已經超出了范圍[left,maxRight]，我們可以確定p[i]的最小值
                //是maxRight - i，至于到底有多大，后面還需要在計算
                p[i] = maxRight - i;
                while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]])
                    p[i]++;
            }
        } else {
            //情況三，i超出了范圍[left,maxRight]，就沒法利用之前的已知資料，而是要一個個判斷了
            p[i] = 1;
            while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]])
                p[i]++;
        }
        //匹配完之后，如果右邊界i + p[i]超過maxRight，那么就更新maxRight和maxCenter
        if (i + p[i] > maxRight) {
            maxRight = i + p[i];
            maxCenter = i;
        }
        //記錄最長回文串的半徑和中心位置
        if (p[i] > resLen) {
            resLen = p[i];
            resCenter = i;
        }
    }
    //計算最長回文串的長度和開始的位置
    resLen = resLen - 1;
    int start = (resCenter - resLen) >> 1;
    //截取最長回文子串
    return s.substring(start, start + resLen);
}

上面都通過畫圖分析很好理解，可能稍微有點不好理解的是后面3行代碼，resLen就是最大回文半徑，resCenter就是最大回文子串（添加特殊字符之后的）中間的那個字符，我們可以根據下面這個圖可以看到，原字串中回文串的長度就是添加特殊字符之后的回文半徑-1，

上面是分為3種情況來判斷的，實際上我們還可以把上面3種情況合并

        //合并后的代碼
        p[i] = maxRight > i ? Math.min(maxRight - i, p[2 * maxCenter - i]) : 1;
        //上面的陳述句只能確定i~maxRight的回文情況，至于maxRight之后的部分是否對稱，
        //就只能一個個去匹配了，匹配的時候首先陣列不能越界
        while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]])
            p[i]++;

我們來看下合并后的最終代碼

// 回傳最長回文串長度
public String longestPalindrome(String s) {
    int charLen = s.length();//源字串的長度
    int length = charLen * 2 + 1;//添加特殊字符之后的長度
    char[] chars = s.toCharArray();//源字串的字符陣列
    char[] res = new char[length];//添加特殊字符的字符陣列
    int index = 0;
    //添加特殊字符
    for (int i = 0; i < res.length; i++) {
        res[i] = (i % 2) == 0 ? '#' : chars[index++];
    }

    //新建p陣列 ，p[i]表示以res[i]為中心的回文串半徑
    int[] p = new int[length];
    //maxRight(某個回文串延伸到的最右邊下標)
    //maxCenter(maxRight所屬回文串中心下標),
    //resCenter（記錄遍歷過的最大回文串中心下標）
    //resLen（記錄遍歷過的最大回文半徑）
    int maxRight = 0, maxCenter = 0, resCenter = 0, resLen = 0;
    //遍歷字符陣列res
    for (int i = 0; i < length; i++) {
        //合并后的代碼
        p[i] = maxRight > i ? Math.min(maxRight - i, p[2 * maxCenter - i]) : 1;
        //上面的陳述句只能確定i~maxRight的回文情況，至于maxRight之后的部分是否對稱，
        //就只能一個個去匹配了，匹配的時候首先陣列不能越界
        while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]])
            p[i]++;
        //匹配完之后，如果右邊界i + p[i]超過maxRight，那么就更新maxRight和maxCenter
        if (i + p[i] > maxRight) {
            maxRight = i + p[i];
            maxCenter = i;
        }
        //記錄最長回文串的半徑和中心位置
        if (p[i] > resLen) {
            resLen = p[i];
            resCenter = i;
        }
    }
    //計算最長回文串的長度和開始的位置
    resLen = resLen - 1;
    int start = (resCenter - resLen) >> 1;
    //截取最長回文子串
    return s.substring(start, start + resLen);
}