前言

马拉车算法是一个能在线性时间能求出最长回文串长度的算法。

个人感觉和kmp也许有异曲同工之妙。


首先,我们的目标是求出最长回文子串的长度

暴力相信大家都会,先是枚举L和R然后O(n)判断每个子串是否是回文串,总时间复杂度$O(n^3)$。

稍微优化一下,枚举中间点mid,贪心地向两端扩展找到最长的$len[i]$,即以i为回文串中心的最大扩展长度。当然,我们发现这样只能处理回文串长度为奇数的情况。所以对于这个暴力,我们有了一个新思路:在两个相邻字符之间插入一个不会出现的字符。

比如aabba,我们把它变成#a#a#b#b#a#,这样每个点向两边扩展出的就一定是奇数长度的$len[i]$了。于是这个暴力的时间复杂度就是$O(n^2)$。下面所使用的字符串也是经过了这样的变换的。

这也正打开了马拉车算法的大门。


众所周知,对暴力算法的优化是对重复计算的优化以及已知信息的利用

先来看重复的计算。

在上面$O(n^2)$的算法中,我们对很多子串进行了重复搜索,最明显的就是,假设i和j都在同一个回文子串内并且关于中心对称,那么$len[j]>=len[i]$。这是显然的。

于是我们考虑设置一个变量$mid$,表示上面那个回文子串的中心,$mr(maxright)$表示这个回文子串的右端点。

哦对了,这个回文子串是当前右端点最大的回文子串,所以叫做maxright。

当我们目前遍历到的i是小于mr的时候,即下图这种情况。

image.png

如图,我们找到i的对称点i',发现可以用 2*mid-i得到,于是 len[i]=len[mid*2-i],但是这个对称只在我们以mid为重心的回文串中可以用,所以 i+len[i]<=mr,len[i]<=mr-i,综合,len[i]=min(len[mid*2-i],mr-i)

接下来是另一种情况,也就是i在mr的右边,i>=mr。

此时,我们没有多余的信息可以利用了,只能以i为重心开始和上面说的一样暴力地拓展找len[i],那么此时我们的i就是新的mid,找到的i+len[i]就是新的mr。

那么这样的时间复杂度为什么是O(n)的呢?

首先考虑i<mr的情况,用了对称性之后基本无法再找到更优的解,所以这一步是O(1)的。

最令人迷惑的就是i>=mr的时候。

看似这样while去找新的len是非常浪费时间的,但是我们在这一步扩展了mr,并且mr会且只会从1被扩展到n,所以mr的扩展总共是O(n)的,mr不扩展的时候也就是i<mr的时候是O(1)的。

于是总的时间复杂度就是O(n)。


模板题代码;

#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define reg register
using namespace std;
const int N=2.2e7+10;
char d[N];
int hw[N],n;
void read(){
    char ch=getchar();
    d[0]=d[++n]='#';
    while(ch<'a'||ch>'z')ch=getchar();
    while(ch>='a'&&ch<='z')d[++n]=ch,d[++n]='#',ch=getchar();
}
void manacher(){
    int mr=0,mid;
    for(int i=1;i<n;i++){
        if(i<mr)hw[i]=min(hw[(mid<<1)-i],mid+hw[mid]-i);
        else hw[i]=1;
        while(d[i+hw[i]]==d[i-hw[i]])hw[i]++;
        if(i+hw[i]>mr)mr=hw[i]+i,mid=i;
    }
}
int main(){
    int ans=1;
    read();
    manacher();
    for(int i=0;i<n;i++)
        ans=max(ans,hw[i]);
    printf("%d\n",ans-1); 
    return 0;
}
最后修改:2021 年 03 月 22 日 03 : 36 PM