要么改变世界,要么适应世界

马拉车算法模板

2021-03-07 11:31:50
79
目录

前言

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

实现

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

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

参考链接:

题目链接: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;
    }
};
历史评论
开始评论