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算法 我真是太弱了