manacher

发表于 更新于 Disqus：

Manacher

求回文串的一个 的算法。笔者退役太久忘记了一些细节，这里重新回顾一下。

首先马拉车只能求奇回文串，因此需要在原串相邻字符间加符号，具体是这么干的：

mambaout -> $#m#a#m#b#a#o#u#t#

这样的话，原串的以字母为中心的奇回文串对应处理后的串中以字母为中心的长度为 的奇回文串。

原串的以字母之间的间隔为中心的偶回文串对应处理后的串中以 # 为中心的长度为 的奇回文串。

然后考虑马拉车算法。马拉车主要基于dp的思想。

遍历处理后的串，假设当前遍历到位置 。

然后在处理的同时维护一个变量 和变量 ，代表以 为中心的回文串，其右边界最远，为 。

然后考虑转移，如果 ，则暴力计算 的情况，然后把 更新为 ， 更新为对应的右边界。

否则可以得知 最短的回文串的情况为 。然后继续暴力拓展。

如果拓展后的右边界大于 则更新 和 。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Manacher(){
    int l = 0;
    Ma[l++] = '$';
    Ma[l++] = '#';
    for(int i = 0; i < n; ++i){
        Ma[l++] = A[i];
        Ma[l++] = '#';
    }
    Ma[l] = 0;
    int mx = 0, id = 0;
    for(int i = 0; i < l; ++i){
        Mp[i] = mx > i ? min(Mp[2*id-i], mx-i):1;
        while(i >= Mp[i] && i+Mp[i] < l && Ma[i+Mp[i]] == Ma[i-Mp[i]]) Mp[i]++;
        if(i + Mp[i] > mx){
            mx = i + Mp[i];
            id = i;
        }
    }
}

由于 最多被更新 次，因此该算法复杂度为 。