马拉车算法模板

前言

马拉车算法是Manacher算法，它是一位名叫Manacher的人在1975年提出的一种算法，用于在线性时间内解决回文串问题。

实现

忙活了一个晚上，终于把这个高效的算法掌握了，该算法时间复杂度为O(N),空间复杂度也为O(N)。

哈哈哈哈哈哈哈，我目前还没有能够把它讲通，有兴趣的可以参考下面的链接进行理解。

参考链接：

• 怎么理解“马拉车“manacher算法？

• Manacher（马拉车）

题目链接：LeetCode-最长回文子串

AC代码

class Solution {
   public:
    string longestPalindrome(string s) { return manacher(s); }
    string manacher(string s) {
        string str = preProcess(s);
        int C = 0, R = 0, i_mirror, len = strlen(str.c_str()), p[2003];
        for (int i = 1; i < len - 1; i++) {
            i_mirror = 2 * C - i;
            if (i < R) {
                // 利用对称性，但是要防止超过右边界
                p[i] = min(p[i_mirror], R - i);
            } else {
                p[i] = 1;
            }
            // 利用中心扩展法进行暴力
            while (str[i + p[i]] == str[i - p[i]]) p[i]++;
            // 判断是否需要更新 R
            if (i + p[i] > R) {
                C = i;
                R = i + p[i];
            }
        }
        // 找出最长回文串的长度并进行截取
        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 1; i < len - 1; i++) {
            if (p[i] > maxLen) {
                maxLen = p[i];
                centerIndex = i;
            }
        }
        int start = (centerIndex - maxLen) / 2;  //原字符串下标
        return s.substr(start, maxLen - 1);
    }
    string preProcess(string s) {
        int len = s.length(), j = 0;
        string t(2003, '\0');
        t[j++] = '^';
        for (int i = 0; i < len; i++) {
            t[j++] = '#';
            t[j++] = s[i];
        }
        t[j++] = '#';
        t[j++] = '$';
        return t;
    }
};