后缀数组+二分+--luoguP3649 [APIO2014]回文串

本文主要是介绍后缀数组+二分+--luoguP3649 [APIO2014]回文串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
首先回文子串可以用$manacher$求出来，并且可以知道开头和长度，那么问题就转化成求一个子串在原串中出现了多少次。

这个可以用$SAM$求（但我还不会

于是就用了$SA$，首先把$h$数组求出来，那么结合$st$表就可以$O(1)$求出一个后缀和另一个后缀的$lcp$，这样看起来是$n^2$的复杂度，但因为$lcp(i,j)=mi{n}_{i+1\le k\le j}(h[k])$这个性质，可以发现一个后缀的$lcp$排名向前向后都是递减的，因此只需要二分出$\ge$这个回文子串长度的一个区间，用$len\times (r-l+1)$算出的就是这个子串的存在值，取$max$就好

有很多细节，也因为手残$wa$了好几次，写$SA$的题一定要脑子清醒啊$qwq$

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 300005
#define LL long long
using namespace std;
int n,m,sa[maxn],rk[maxn],tp[maxn],tax[maxn],h[maxn];
int len[maxn<<1],f[maxn][20];
char s[maxn],tmp[maxn<<1];
LL ans;inline void rsort(){for(int i=0;i<=m;i++) tax[i]=0;for(int i=1;i<=n;i++) ++tax[rk[i]];for(int i=1;i<=m;i++) tax[i]+=tax[i-1];for(int i=n;i;i--) sa[tax[rk[tp[i]]]--]=tp[i];
}inline void ssort(){for(int i=1;i<=n;i++) rk[i]=s[i],tp[i]=i;rsort();for(int w=1,p=0;w<=n && p<n;w<<=1,m=p){p=0;for(int i=n-w+1;i<=n;i++) tp[++p]=i;for(int i=1;i<=n;i++)if(sa[i]>w) tp[++p]=sa[i]-w;rsort(); swap(rk,tp);rk[sa[1]]=p=1;for(int i=2;i<=n;i++)if(tp[sa[i]]==tp[sa[i-1]]&&tp[min(n+1,sa[i]+w)]==tp[min(n+1,sa[i-1]+w)])rk[sa[i]]=p;else rk[sa[i]]=++p;}
}inline void geth(){int j,k=0;for(int i=1;i<=n;i++){if(k) --k;j=sa[rk[i]-1];while(s[j+k]==s[i+k]) ++k;h[rk[i]]=k;}
}inline int init(char *p){tmp[0]='@';for(int i=1;i<=n;i++) tmp[(i<<1)-1]='#',tmp[i<<1]=s[i];tmp[2*n+1]='#';return 2*n+1;
}inline void prework(){for(int i=1;i<=n;i++) f[i][0]=h[i];for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}inline int query(int l,int r){if(l>r) swap(l,r); ++l;int t=log2(r-l+1);return min(f[l][t],f[r-(1<<t)+1][t]);
}inline int find_fr(int now,int len){int l=1,r=now-1,mid;while(l<=r){mid=(l+r)>>1;if(query(mid,now)>=len) r=mid-1;else l=mid+1;} return l;
}inline int find_bh(int now,int len){int l=now+1,r=n,mid;while(l<=r){mid=(l+r)>>1;if(query(now,mid)>=len) l=mid+1;else r=mid-1;} return r;
}inline LL solve(int s,int ln){int pre=s;int ll,rr; s=rk[s];if(h[s]<ln) ll=s;else ll=find_fr(s,ln);if(h[s+1]<ln) rr=s;else rr=find_bh(s,ln);return 1LL*ln*(rr-ll+1);
}inline void manacher(char *p,int ll){int mx=0,ps=0;for(int i=1;i<=ll;i++){if(mx>i) len[i]=min(mx-i,len[2*ps-i]);else len[i]=1;while(p[i-len[i]]==p[i+len[i]]) {if(p[i-len[i]]!='#') {++len[i];continue;}//!!!++len[i];if(i+len[i]>mx) ans=max(ans,solve(i/2-len[i]/2+1,len[i]-1));}if(len[i]+i>mx) mx=len[i]+i,ps=i;}
}int main(){scanf("%s",s+1); n=strlen(s+1); m=127;ssort(); geth(); prework(); manacher(tmp,init(s));printf("%lld\n",ans);return 0;
}

这篇关于后缀数组+二分+--luoguP3649 [APIO2014]回文串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---