马拉车算法

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

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 ) O(n) 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);
    }
};