[数据结构与算法]马拉车算法

马拉车算法

问题：求一个给定字符串的最长回文子串。

1. 原理

原理

• manacher算法专门用于解决给定字符串的最长回文子串。

• 首先马拉车算法只能求解长度为奇数的最长回文子串，因此需要将原串变化为新串，变换规则如下：在原串的首尾分别加上$#和#^，然后相邻的两个字母之间加上#，如下图：

• 原串为a，新串为b，可以发现新串所有的回文串都是奇数长度的，假设在新串中以b[i]为中心的最长回文串的长度为len，则在原串中对应的回文串长度为len-1。

• 因此我们只需要求出新串所有回文串的半径，找到值最大的一个，减去一就得到最长回文串的长度。现在问题变为了如何求解以b[i]为中心的回文串的半径。

• 用数组p表示回文串的半径，例如：p[i]: 以b[i]为中心的回文串的半径。

• 假设当前得到的最靠右的回文串的中心是mid，右侧边界位置为mr-1，现在分为两种情况讨论：

（1）如果当前考虑的中心坐标i在(mid, mr)之间，则p[i]至少为min(p[mid * 2 - i], mr - i)，原因如下：

另外i一定是大于mid，这是因为我们从左向右遍历i，每次会用i更新mid。

（2）否则i>=mr，此时以b[i]为中心的回文串长度p[i]=1即可。

• 之后更新以b[i]为中心的回文串长度，并更新mr和mid。

• 此做法的时间复杂度是$O(n)$的。虽然代码中有两重循环，但是内层循环最多执行n次。

2. 例题

AcWing 3188. manacher算法

问题描述

• 问题链接：AcWing 3188. manacher算法

  

分析

• 使用马拉车算法求解出长度即可。

代码

• C++

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2e7 + 10;

int n;
char a[N], b[N];  // a: 原串  b: 转化后的字符串
int p[N];  // p[i]: 以b[i]为中心的回文串的半径

void init() {  // 假设原串为aka, 新串为 $#a#k#a#^
    
    int k = 0;
    b[k++] = '$', b[k++] = '#';
    for (int i = 0; i < n; i++) b[k++] = a[i], b[k++] = '#';
    b[k++] = '^';
    n = k;
}

void manacher() {
    
    int mr = 0, mid;  // 当前得到的最靠右的回文串为 b(2*mid-mr ~ mr)
    for (int i = 1; i < n; i++) {
        if (i < mr) p[i] = min(p[mid * 2 - i], mr - i);
        else p[i] = 1;
        
        while (b[i - p[i]] == b[i + p[i]]) p[i]++;
        
        if (i + p[i] > mr) {
            mr = i + p[i];
            mid = i;
        }
    }
}

int main() {
    
    scanf("%s", a);
    n = strlen(a);
    
    init();
    
    manacher();
    
    int res = 0, start = 0;  // start: 回文串起始位置
    for (int i = 0; i < n; i++) res = max(res, p[i]);
    
    printf("%d\n", res - 1);
    
    return 0;
}

Leetcode 0005 最长回文子串

问题描述

• 问题链接：Leetcode 0005 最长回文子串

  

分析

• 本题需要求解这个最长回文子串，如果在新串中p[i]取得了最大值，则最长回文子串的长度为len=p[i]-1。

• 最长回文子串在原串中的起始位置为i / 2 - 1 - (len - 1) / 2。

代码

• C++

class Solution {
public:
    string longestPalindrome(string s) {
        string t = "$#";
        for (auto c : s) t += c, t += '#';
        t += '^';

        // manacher
        int n = t.size();
        vector<int> p(n + 10, 0);
        int mr = 0, mid;
        for (int i = 1; i < n; i++) {
            if (i < mr) p[i] = min(p[mid * 2 - i], mr - i);
            else p[i] = 1;

            while (t[i - p[i]] == t[i + p[i]]) p[i]++;

            if (i + p[i] > mr) {
                mr = i + p[i];
                mid = i;
            }
        }

        // 求解最长回文子串起始位置和长度
        int len = 0, start = 0;
        for (int i = 0; i < n; i++) {
            p[i]--;
            if (p[i] > len) {
                len = p[i];
                start = i / 2 - 1 - (len - 1) / 2;
            }
        }

        return s.substr(start, len);
    }
};