Manacher总结

FREEH · 2018-07-24 22:21:57 · 题解

Manacher总结

【用途】

• 求一个字符串中有多少个回文子串。

【算法过程】

1. 预处理

• 由于回文串分为偶回文串和奇回文串，奇偶判断起来比较麻烦，因此我们可以在字符串的首、尾以及各个字符之间添加一些“神奇”字符（不妨使用$），但是要注意字符串的首添加的字符必须区别于各个字符之间的字符。
• 不难发现，修改后的字符串都变成了奇字符串。
• 以下Manacher算法的所有处理都是基于修改后的字符串。

2. Manacher算法的主体

• 定义数组p[i]表示以字符i为回文中心的最长回文串的半径，不难发现，p[i]-1就是字符串中最长回文串的长度（因为要去除$）。
• 定义mx和mid，表示目前找到的回文串的右端的最右是mx，中心是mid。
• 如上图所示，id是j~mx的回文中心，因此以i的对称点为回文中心的字符串=以i为回文中心的字符串，因此p[i]可以是p[j]。但是由于超过mx的部分（即右红边部分）不能保证必定等于左红边的部分，所以p[i]不能超过i~mx的长度。因此

  p[i]=min(mx-i,p[mid*2-i])

• 接下来，我们就要暴力统计右侧 “不能保证” 的部分，即最右黑边的右侧是否满足回文性质（具体看代码）。
• 最后更新一下mx即可。

【时空复杂度】

• Manacher算法的时间复杂度为O(n)（这里就不作证明了），因此是解决回文问题的利器。

【参考程序】

#include<cstdio>
#include<cstring>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
char s[32000005],st[32000005];
int p[32000005];
int change()
{
    int len=strlen(st);
    int j=2;
    s[0]='^';
    s[1]='$';
    for (int i=0;i<len;i++)
    {
        s[j++]=st[i];
        s[j++]='$';
    }
    s[j]='&';
    return j;
}
int Manacher()
{
    int len=change(),mid=1,mx=1,ans=-1;
    for (int i=1;i<len;i++)
    {
        if (i<mx)
            p[i]=min(mx-i,p[mid*2-i]);
        else
            p[i]=1;
        while (s[i-p[i]]==s[i+p[i]])
            p[i]++;
        if (mx<i+p[i])
        {
            mid=i;
            mx=i+p[i];
        }
        ans=max(ans,p[i]-1);
    }
    return ans;
}
int main()
{
    scanf("%s",st);
    printf("%d",Manacher());
}