【模板】manachar

马拉车算法用于解决最长回文字串的一类问题，可以将时间复杂度降低为\(O(n)\)，几乎达到了理论上的下界。

核心思想：将分奇偶讨论的情况转化成同一种情况（奇数）。

下面介绍该算法需要用到的几点性质：

\(p[i]\)表示以\(i\)为中心的派生串最长回文半径的长度，则\(p[i]-1\)表示原串中以\(i\)为中心的最长回文子串的长度。

证明：在派生串T中，所有回文字串的长度都为奇数，那么对于以\(i\)为中心的最长回文字串，其长度就为\(2*P[i]-1\)，经过观察可知，T中所有的回文子串，其中分隔符的数量一定比其他字符的数量多1，也就是有\(P[i]\)个分隔符，剩下\(P[i]-1\)个字符来自原字符串，所以该回文串在原字符串中的长度就为\(P[i]-1\)。
在计算以添加字符为中心的回文串时，原串的回文长度为偶数，以原串中字符为中心时答案为奇数。
以 \(id\) 为中心，\(i\)的对称点的坐标公式为\((id<<1)-i\)
正常回文序列的子回文序列（包括自身）为\((p[i]-1)>>1\)

/*

	马拉车算法模板

*/

#include <bits/stdc++.h>

using namespace std;

const int maxn=3e7+10;

char s[maxn],str[maxn];

int n,ans,p[maxn];

void init(){

    str[0]=str[1]='#';

    for(int i=1;i<=n;i++)str[i<<1]=s[i],str[i<<1|1]='#';

    n=(n<<1)+2;str[n--]=0;

}

void manachar(){

    int id=0,mx=0;

    for(int i=1;i<=n;i++){

        p[i]=mx>i?min(mx-i,p[(id<<1)-i]):1;

        while(str[i+p[i]]==str[i-p[i]])p[i]++;

        if(i+p[i]>mx)mx=i+p[i],id=i;

    }

}

int main(){

    scanf("%s",s+1);

    n=strlen(s+1);

    init();manachar();

    for(int i=1;i<=n;i++)ans=max(ans,p[i]);

    printf("%d\n",ans-1);

    return 0;

}

巴特西

【模板】manachar

最新文章

热门文章