PAT甲题题解-1040. Longest Symmetric String (25)-求最长回文子串

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

博主欢迎转载，但请给出本文链接，我尊重你，你尊重我，谢谢~
http://www.cnblogs.com/chenxiwenruo/p/6789177.html
特别不喜欢那些随便转载别人的原创文章又不给出链接的
所以不准偷偷复制博主的博客噢~~

给出一个字符串，让你找出其中最长的回文子串的长度
因为长度最多1000，其实暴力枚举也可以
对于第i个字符，往前、往右找，统计能够达到的最大回文长度，for一遍即可
然而如果对应大数据就不行了，所以这里还是用了
Manacher算法 O(n) 求最长回文子串
不会的还是建议戳一下链接学习一下

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <cmath>

using namespace std;

const int M = *;

char str[M];//start from index 1

int p[M];

char s[M];

int n;

void checkmax(int &ans,int b){

    if(b>ans) ans=b;

}

inline int min(int a,int b){

    return a<b?a:b;

}

void pk(){

    int i;

    int mx = ;

    int id;

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

        if( mx > i )

            p[i] = min( p[*id-i], p[id]+id-i );

        else

            p[i] = ;

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

        if( p[i] + i > mx ) {

            mx = p[i] + i;

            id = i;

        }

    }

}

void pre()

{

    int i,j,k;

    n = strlen(s);

    str[] = '$';

    str[] = '#';

    for(i=;i<n;i++)

    {

        str[i* + ] = s[i];

        str[i* + ] = '#';

    }

    n = n* + ;

    str[n] = ;

}

void pt()

{

    int i;

    int ans = ;

    for(i=;i<n;i++)

        ans=max(ans,p[i]);

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

}

int main()

{

    gets(s);

//printf("%s\n",s);

    pre();

    pk();

    pt();

    return ;

}