BZOJ 2565 最长双回文串 Manacher

题目

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S。

Output

一行一个整数，表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

12

题解

这道题是我写了一整天的一道题，也就是说我几乎一天都在写这题。。。由于我非常的弱，我后来才发现可以在Manacher的过程中求出一些很有用的东西，下文将会予以论述，而我要是和Manacher一起求出来的话那么感觉就会非常的好

就是，这道题其实非常的水，我们只要先Manacher一下，然后求出一个位置的左边的右端点为这个字符的最长回文串的长度，不妨存入 Left 数组，右侧同理，存入 Right 数组，然后我们求 Ans=max(Ans,Left[i]+Right[i+1]),i∈(0,len−1) 即可

代码

让注释记录我思维无力的挣扎

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 100005
using namespace std;
int f[maxn*2],len1,pre[maxn*2],suf[maxn*2],len;
char txt[maxn],s[maxn*2];
void Manacher(){
    for(int i=0;i<len1;i++){
        s[i<<1]='@';
        s[(i<<1)+1]=txt[i];
    }
    s[(len1)<<1]='@';
    len=2*len1+1;
    int mx=0,p=0;
    for(int i=0;i<len;i++){
        if(mx>i) f[i]=min(mx-i,f[2*p-i]);
        else f[i]=0;
        while(i+f[i]+1<len&&i-f[i]-1>=0&&s[i+f[i]+1]==s[i-f[i]-1]) f[i]++;
        if(f[i]+i>mx){
            mx=f[i]+i;
            p=i;
        }
    }
    return;
}
void process(){
    for(int i=0;i<len;i++){
        if(i&1){
            f[i]=((f[i]>>1)<<1)+1;
        }else{
            f[i]=((f[i]+1)>>1)<<1;
        }
    }
    int now=-1;
    for(int i=1;i<len-1;i++){
        if(i&1){
            if((i>>1)>now){
                pre[++now]=1;
            }
            while(((i>>1)+(f[i]>>1))>now){
                now++;
                pre[now]=((now-(i>>1))<<1)+1;
            }
        }
        else{
            if((i>>1)>now){
                pre[++now]=1;
            }
            while(((i>>1)+(f[i]>>1)-1)>now){
                now++;
                pre[now]=(now-(i>>1)+1)<<1;
            }
        }
    }
    now=len1;
    for(int i=len-2;i>0;i--){
        if(i&1){
            if((i>>1)<now){
                suf[--now]=1;
            }
            while(((i>>1)-(f[i]>>1))<now){
                now--;
                suf[now]=(((i>>1)-now)<<1)+1;
            }
        }
        else{
            if((i>>1)<now){
                suf[--now]=1;
            }
            while(((i>>1)-(f[i]>>1))<now){
                now--;
                suf[now]=(-now+(i>>1))<<1;
            }
        }
    }
    /*int now=0; for(int i=0;i<len1;i++){ if(f[2*i]-1+i>f[2*i+1]+i){ while(f[2*i]-1+i>now){ pre[now]=((now-i)<<1)+1; now++; } } else{ while(f[2*i+1]+i>now){ pre[now]=(now-i)<<1; now++; } } } pre[0]=1; now=len1-1; for(int i=len1-1;i>=0;i--){ if(i-f[2*i]+1<i-f[2*i+1]+1){ while(i-f[2*i]+1<now){ suf[now]=((i-now)<<1)+1; now--; } } else{ while(i-f[2*i+1]+1<now){ suf[now]=(i-now+1)<<1; now--; } } } suf[len-1]=1; int ans=0; for(int i=0;i<len1;i++){ ans=max(ans,pre[i]+suf[i+1]); } printf("%d",ans); return;*/
    /*int now=0; for(int i=0;i<len;i++){ while(i+f[i]>now){ if(i>=now){ pre[now]=1; now++; continue; } if(!(i&1))pre[now]=(((now-i)>>1)<<1)+1; else pre[now]=(((now-i+1)>>1)<<1); now++; } } now=len-1; for(int i=len-1;i>=0;i--){ while(i-f[i]<now){ if(i<=now){ suf[now]=1; now--; continue; } if(!(i&1))suf[now]=(((i-now)>>1)<<1)+1; else suf[now]=(((i-now+1)>>1)<<1); now--; } } suf[0]=1;*/
    /*int now=0; for(int i=0;i<len;i++){ while(i+f[i]>now){ now++; pre[now]=((now-i)<<1)+1; } } for(int i=0;i<len;i++){ if(!(i&1))pre[i]>>=1; else pre[i]=(pre[i]+1)>>1; } now=len-1; for(int i=len-1;i>=0;i--){ while(i-f[i]<now){ now--; suf[now]=((i-now)<<1)+1; } } for(int i=len-1;i>=0;i--){ if(!(i&1))suf[i]>>=1; else suf[i]=(suf[i]+1)>>1; }*/
    int ans=0;
    for(int i=0;i<len1-1;i++){
        ans=max(ans,pre[i]+suf[i+1]);
    }
    printf("%d",ans);
    return;
}
int main(){
    /*freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);*/
    scanf("%s",txt);
    len1=strlen(txt);
    Manacher();
    process();
    return 0;
}

细节

我实在不知道怎么说，满屏的细节QAQ

总结

要灵活地运用Manacher算法
我真是太弱了