回文串

思路

这道题我先写了马拉车（不会的可以去学一学，能以O(n)复杂度求最长回文串长度），A了之后看数据范围，发现暴力也是能过的。需要注意点一些细节：（我被坑过的点）
马拉车记得在要在字符串前面加多一个字符防止越界。
暴力算法不要列举区间再判断是否回文，先列举中心点再求回文长度更快。同时注意字符串长度的奇偶性。

暴力代码

#include<bits/stdc++.h>
using namespace std;
int main() {
    char s[1205];
    while(scanf("%s",s)!=EOF){
        int len=strlen(s),maxx=0;
        for(int i=0;i<len;i++){
            int len2=1,len3=0;
            while(i-len2>=0&&i+len2<len&&s[i-len2]==s[i+len2]) len2++;
            while(i-len3>=0&&i+1+len3<len&&s[i-len3]==s[i+1+len3]) len3++;
            maxx=max(maxx,max(len2*2-1,len3*2));
        }
        cout<<maxx<<endl;
    }
    return 0;
}

Manacher代码

#include<bits/stdc++.h>
using namespace std;

int len[3000],len2;

int manacher(char str[],int len2){
    int mx=0,id=0,maxx=0;
    for(int i=1;i<len2;i++){
        if(mx>i) len[i]=min(len[2*id-i],mx-i);
        else len[i]=1;
        while(str[i-len[i]]==str[i+len[i]]) len[i]++;
        if(i+len[i]>mx){
            id=i;
            mx=i+len[i];
        }
        maxx=max(len[i],maxx);
    }
    return maxx-1;
}

int main(){
    char s[1200];
    while(scanf("%s",s)!=EOF){
        char str[3000];
        memset(len,0,sizeof(len));
        str[0]='$';
        str[1]='#';
        len2=1;
        for(int i=0;i<strlen(s);i++){
            str[++len2]=s[i];
            str[++len2]='#';
        }
        str[len2+1]=0;
        printf("%d\n",manacher(str,len2));
    }

    return 0;
}