Description

考慮一個只包含小寫拉丁字母的字符串s。我們定義s的一個子串t的“出
現(xiàn)值”為t在s中的出現(xiàn)次數(shù)乘以t的長度。請你求出s的所有回文子串中的最
大出現(xiàn)值。

Input

輸入只有一行，為一個只包含小寫字母(a -z)的非空字符串s。

Output

輸出一個整數(shù)，為回文子串的最大出現(xiàn)值。

Sample Input

abacaba

Sample Output

7

Solution

SA+manacher。

考慮\(manacher\)的過程中，本質不同的回文串只會在每次擴展的時候出現(xiàn)，所以每次擴展的時候上下二分，然后算一下就好了。

復雜度\(O(n\log n)\)。

注意\(manacher\)之前會把原串翻倍，在翻倍之前就把\(sa\)建好，否則卡不過。。

(其實這題正解是回文自動機來著。。那玩意貌似是O(n)的)

#pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std;void read(int &x) {x=0;int f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; }#define ll long long void print(ll x) {if(x<0) putchar('-'),x=-x;if(!x) return ;print(x/10),putchar(x%10+48); } void write(ll x) {if(!x) putchar('0');else print(x);putchar('\n');}const int maxn = 6e5+10;char c[maxn],s[maxn]; int n,f[maxn]; ll ans;int spx[maxn],spy[maxn],sum[maxn],sa[maxn],m,rk[maxn],height[maxn],st[maxn][20],lg[maxn],len;void get_sa() {m=240;int p=0,*x=spx,*y=spy;for(int i=1;i<=n;i++) sum[x[i]=c[i]]++;for(int i=1;i<=m;i++) sum[i]+=sum[i-1];for(int i=n;i;i--) sa[sum[x[i]]--]=i;for(int tot=0,k=1;p<n;k<<=1,tot=0) {p=0;for(int i=n-k+1;i<=n;i++) y[++tot]=i;for(int i=1;i<=n;i++) if(sa[i]>k) y[++tot]=sa[i]-k;for(int i=1;i<=m;i++) sum[i]=0;for(int i=1;i<=n;i++) sum[x[y[i]]]++;for(int i=1;i<=m;i++) sum[i]+=sum[i-1];for(int i=n;i;i--) sa[sum[x[y[i]]]--]=y[i];swap(x,y);x[sa[1]]=p=1;for(int i=2;i<=n;i++)if(y[sa[i]]!=y[sa[i-1]]||y[sa[i]+k]!=y[sa[i-1]+k]) x[sa[i]]=++p;else x[sa[i]]=p;m=n;} }void get_height() {for(int i=1;i<=n;i++) rk[sa[i]]=i;int p=1;for(int i=1;i<=n;i++) {if(p) p--;while(c[i+p]==c[sa[rk[i]-1]+p]) p++;height[rk[i]]=p;} }void rmq_init() {for(int i=1;i<=n;i++) st[i][0]=height[i];for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;for(int i=1;i<=18;i++)for(int j=1;j<=n;j++)st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]); }int get_rmq(int l,int r) {if(r<l) return r=l;int w=lg[r-l+1];return min(st[l][w],st[r-(1<<w)+1][w]); }void get_ans(int lpos,int rpos,int xx) {if(s[lpos]=='&') return ;lpos/=2,rpos/=2;int w=rk[lpos];int l=1,r=w,ret=w,mid,Len=rpos-lpos+1;while(l<=r) {mid=(l+r)>>1;if(get_rmq(mid+1,w)>=Len) ret=mid,r=mid-1;else l=mid+1;}int ret2=w;l=w,r=len;while(l<=r) {mid=(l+r)>>1;if(get_rmq(w+1,mid)>=Len) ret2=mid,l=mid+1;else r=mid-1;}ans=max(ans,1ll*(ret2-ret+1)*xx); }int main() {char e=getchar();while(e!=EOF&&e!='\n') c[++len]=e,e=getchar();n=len;get_sa(),get_height(),rmq_init();s[n=0]='$',s[++n]='&';for(int i=1;i<=len;i++) s[++n]=c[i],s[++n]='&';int mr=1,mid=1;for(int i=1;i<=n;i++) {f[i]=min(mr-i,f[mid*2-i]);while(s[i-f[i]]==s[i+f[i]]) get_ans(i-f[i],i+f[i],f[i]+1),f[i]++;if(i+f[i]>mr) mr=i+f[i],mid=i;}write(ans);return 0; }

轉載于:https://www.cnblogs.com/hbyer/p/10284595.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的[bzoj3676] [APIO2014]回文串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。