51 Nod 1089 最长回文子串（Manacher算法)

基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。

输入一个字符串Str，输出Str里最长回文子串的长度。

Input

输入Str（Str的长度 <= 100000)

Output

输出最长回文子串的长度L。

Input示例

daabaac

Output示例

#include<bits/stdc++.h>

#include<stdio.h>

#include<iostream>

#include<cmath>

#include<math.h>

#include<queue>

#include<set>

#include<map>

#include<iomanip>

#include<algorithm>

#include<stack>

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn=110010;

char Ma[maxn*2];

int Mp[maxn*2];

void Manacher(char s[],int len)

{

    int l=0;

    Ma[l++]='$';

    Ma[l++]='#';

    for(int i=0;i<len;i++)

    {

        Ma[l++]=s[i];

        Ma[l++]='#';

    }

    Ma[l]=0;

    int mx=0,id=0;

    for(int i=0;i<l;i++)

    {

        Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;

        while(Ma[i+Mp[i]]==Ma[i-Mp[i]])Mp[i]++;

        if(i+Mp[i]>mx)

        {

            mx=i+Mp[i];

            id=i;

        }

    }

}

char s[maxn];

int main()

{

#ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

#endif // ONLIN

    while(scanf("%s",s)==1)

    {

        int len=strlen(s);

        Manacher(s,len);

        int ans=0;

        for(int i=0;i<2*len+2;i++)

            ans=max(ans,Mp[i]-1);

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

    }

    return 0;

}

巴特西

51 Nod 1089 最长回文子串（Manacher算法)

最新文章

热门文章