开始直接暴力,TLE了,然后就去百度了这个马拉车算法。其实思想也很简单的,就是在我们普通的思想上进行了优化,减少了查询次数。

按照我们普通的思路来做,肯定是找一个点然后往左右两边延伸找最长,当然这里面涉及到了偶数回文、边界判断等特殊处理,虽然TLE了,但是对接下来理解“马拉车”算法却容易了。

首先,为了处理偶数问题,我们在字符串中插入一些特殊字符,比如”#“,注意第一个字符给另外一个比如”@“来特判边界,最后一个不用特判了,因为C中有”\0“。这样就解决了偶数问题。

然后,马拉车算法就是判断一个点之后,把这个点所能延伸到的右边最远处标记一下,以及当前能延伸到最远的这个下标id。然后再判断i=id+x时,i=id-x肯定已经处理完了不,肯定得到了id-x的最长长度,然后因为对称性,我们就能不总是慢慢的从两边开始+1出发搜索了,而是在i=id-x的宽度上再进行暴力搜索(当然,这里有个边界值要处理,就是当前i到最长点的距离和i=id-x的距离,取最小的,至于为什么,自己想想就知道了),这样就减少了搜索量,避免TLE。

给一个好理解的博客链接:manacher算法详解


我的代码:


StatusAccepted
Time483ms
Memory2652kB
Length785
LangG++


#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 110005
int ans, lenr, lens, mx, id, pd[MAX*2];
char res[MAX*2], str[MAX*2];
void init(){
    lenr=strlen(res);
    str[0]='@';
    str[1]='#';
    for(int i=0;i<lenr;i++){
        str[i*2+2]=res[i];
        str[i*2+3]='#';
    }
    lens=lenr*2+2;
}
void manacher(){
    mx=0;id=0;ans=0;
    for(int i=1;i<lens;i++){
        if(mx>i)pd[i]=min(pd[2*id-i], mx-i);
        else pd[i]=1;
        for(;str[i+pd[i]]==str[i-pd[i]];pd[i]++);
        if(i+pd[i]>mx){
            mx=i+pd[i];id=i;
        }
        ans=max(ans, pd[i]-1);
    }
}
int main()
{
    while(~scanf("%s", res)){
        init();
        manacher();
        printf("%d\n", ans);
    }
    return 0;
}