HDU - 3068 最长回文(manacher模板题)-蒲公英云

HDU - 3068 最长回文(manacher模板题)

点我看题

题意：求给定的一串字符串中最长的回文子串。

分析：manacher(马拉车模板题。

推荐学习博客：https://www.cnblogs.com/grandyang/p/4475985.html

参考代码:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 110000+10;
int n;
char s[maxn<<1];
int p[maxn<<1];
void manacher()
{
    memset(p,0,sizeof(p));
    n = strlen(s);
    for( int i = n; i >= 0; i--)
    {
        s[i*2+2] = s[i];
        s[i*2+1] = '#';
    }
    s[0] = '$';
    //mx代表以id为中心，能延伸到的最右位置
    int id, mx = 0;
    for( int i = 1; i < 2*n+1; i++)
    {
        if( mx > i)
            p[i] = min(p[2*id-i],mx-i);//如果到达最远的位置大于当前匹配的地方，则p[i]取min(id的对称点的p,到达最远的距离-i)
        else
            p[i] = 1;//如果i在mx的右方，则p[i]=1
        while( s[i-p[i]] == s[i+p[i]])//判断i的回文长度，继续向两边延伸
            p[i]++;
        if( i+p[i] > mx)//看是否要更新最远距离，如果要，将此点作为中心
        {
            id = i;
            mx = p[i]+i;
        }
    }
}
int main()
{
    while( ~scanf("%s",s))
    {
        manacher();
        int ans = -INF;
        for( int i = 0; i < 2*n+1; i++)
            ans = max(ans,p[i]);
        printf("%d\n",ans-1);
    }
    return 0;
}