1040. Longest Symmetric String (25)

题目链接：https://www.patest.cn/contests/pat-a-practise/1040
解题思路：manecher算法
这是专门处理回文串的算法，算法笔记上是用动态规划解决的，可能是怕读者暂时不能理解，但是不得不说manecher算法非常的巧妙，时间复杂度只要O(n)，而且代码短的可怕，主要是不难，我建议去看看牛客网上左程云老师讲的manecher算法，很容易就听懂了。这道题就是manecher算法的一个裸模板，没什么好说的，建议学习这个算法。其实中间的代码还可以更简洁些，但是我担心我以后看不懂，尽量写得详细了一些。

#include <cstdio>
#include <cstring>
const int maxn = 4010;
char str[maxn],s[maxn/2];
int p[maxn];
int main(){
    gets(s);
    str[0]='$';
    str[1]='#';
    int k = 2;
    for(int i=0;s[i]!='\0';i++){
        str[k++]=s[i];
        str[k++]='#';
    }
    str[k]='\0';
    int mx=0,id=0,max=1;
    memset(p,0,sizeof(p));
    int len = strlen(str);
    for(int i=1;i<=len;i++){
        if(mx>i){                //i在mx覆盖的半径内 
            if(mx-i>p[2*id-i]){      //p[j]在左大内 
                p[i]=p[2*id]; 
            }else{             //p[j]超过了左大 
                p[i]=mx - i; 
            }
        }else {
            p[i]=1; 
        } 
        while(str[i+p[i]]==str[i-p[i]]) p[i]++;
        if(i+p[i] > mx){
            mx = i + p[i];
            id = i; 
        }
        if(max < p[i]) max =p[i];
    }
    printf("%d\n",max-1);
    return 0;
}