一文让我彻底明白马拉车算法

· · 个人记录

先放一个链接 Link

首先，马拉车算法是为了解决最大回文串的问题而产生的，时间复杂度为 O(n)

定义一个数组 P_i , 代表以第 i 个字符为中心向外扩展所能扩展出的最大半径

定义 R 代表包含了第 i 个字符的最右边的字符串的最右边的字符的坐标

'R' means the address of the rightest letter of the axisymmetric(轴对称的) string which includes the i-th letter.

定义 C 代表包含了第 i 个字符的最右边的字符串的对称轴位置

'C' means the address of the axis of symmetry of the axisymmetric(轴对称的) string which includes the i-th letter.

It's easy to find out that R and C are in the same string.
Amazed!

那么如何求出P_i呢？

We can define i\_mirror as the symmetric letter of i of C,so i\_mirror=2\times C - i.

And in some cases P_i=P_{i\_mirror}.

We only think about the cases in which P_i doesn't equal to P_{i\_mirror}

There are two cases.

  1. 当前以 i 为中心的回文串的右端点超过了R，即i+P_{i\_mirror}>R

非常优美的算法，非常简洁的代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6 + 9;
int len,C,R,maxlen;
int P[N<<1];
char c[N],T[N<<1];
int main()
{
    scanf(" %s",c+1);
    T[0]='^';
    len=strlen(c+1);
    for(int i=1;i<=len;i++){
        T[i*2-1]='#';
        T[i*2]=c[i];
    }
    T[2*len+1]='#';
    T[2*len+2]='&';
    for(int i=2;i<=2*len;i++){
        int i_mirror;
        i_mirror=2*C-i;
        if(R>i){
            P[i]=min(R-i,P[i_mirror]);
        }
        else{
            P[i]=0;
        }
        while(T[i+P[i]+1]==T[i-P[i]-1]){
            P[i]++;
        }
        if(i+P[i]>R){
            C=i;
            R=i+P[i];
        }
    }
    for(int i=2;i<=2*len;i++){
        if(P[i]>maxlen){
            maxlen=P[i];
        }
    }
    printf("%d\n",maxlen);
    return 0;
}