【題解】【切開字符串】
P8631 [藍(lán)橋杯 2015 國 AC] 切開字符串
Sol
首先問題可以轉(zhuǎn)化為對每個前綴求出本質(zhì)不同奇回文子串?dāng)?shù)，和對每個后綴求出本質(zhì)不同子串?dāng)?shù)和本質(zhì)不同奇回文子串?dāng)?shù)。
本質(zhì)不同子串?dāng)?shù)
對每個后綴求出本質(zhì)不同子串?dāng)?shù)，考慮后綴數(shù)組。對于從位置\(i\)開始的后綴，這個后綴的本質(zhì)不同子串?dāng)?shù)即為把\(i,i+1,\cdots ,n\)后綴排序后，兩兩相鄰的\(LCP\)，于是可以從后往前把每個后綴不斷加進(jìn)去，每加入一個后綴，就把跟他相鄰的后綴的貢獻(xiàn)更新，因?yàn)槊看涡枰閰^(qū)間\(min\)，所以要用\(st\)表維護(hù)。但是換個枚舉順序，考慮從\(1\)開始，不斷從集合中刪去\(1,2,3,\cdots\)的后綴，因?yàn)閮牲c(diǎn)之間的\(min\)的范圍不斷變大，只需用鏈表就可以線性維護(hù)。
本質(zhì)不同奇回文子串?dāng)?shù)
對于本質(zhì)不同奇回文子串?dāng)?shù)，首先有個結(jié)論：長度為\(n\)的字符串最多有\(n\)個本質(zhì)不同的回文子串。
證明：
考慮把每個本質(zhì)不同的回文子串記錄在其第一次出現(xiàn)的位置的右端點(diǎn)上。
假設(shè)右端點(diǎn)\(r\)上,存在兩個長度不同的回文子串，長度分別為\(p,q\)，不妨設(shè)\(p<q\),那么由于兩個串都回文，可以得到長度為\(p\)的串在\(i-q+p\)就出現(xiàn)過，與前提矛盾，因此每個右端點(diǎn)最多記錄一個回文子串。
求法：
通過證明可以看出每個位置記錄的回文子串一定是最長的那個，先通過manacher對每個回文中心\(x\)求出其回文半徑\(p_x\)，然后對每個\((x,p_x)\)，令\([x,x+p_x-1]\)對x取min，最后每個位置得到的即為最長的奇回文子串的回文中心，把每個右端點(diǎn)對應(yīng)的回文子串hash一下，就可以統(tǒng)計每個前綴中本質(zhì)不同的奇回文子串?dāng)?shù)。區(qū)間取min發(fā)現(xiàn)可以拓展到一個前綴取min，因此，也可以做到線性。
總結(jié)：
如果求后綴數(shù)組使用線性做法的話，整道題的復(fù)雜度即為\(O(n)\),不過筆者比較菜，這里用的倍增寫法。
Code
點(diǎn)擊查看代碼
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
int rd()
{
int x=0,w=1;
char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*w;
}
const int N=2e5+100;
int n,sa[N],rk[N],h[N],y[N],t[N],pre[N],suf[N],p[N],f[2][N];
char s[N];
long long w[N];
const int P=37;
unsigned long long hs[N],pw[N];
int val[N];
unordered_map<unsigned long long ,int>mp[N];
int geths(int l,int r)
{
return hs[r]-hs[l-1]*pw[r-l+1];
}
void manacher()
{
p[1]=1;
int id=1,mx=2;
for(int i=2;i<=n;++i)
{
p[i]=min(mx-i,p[(id<<1)-i]);
while(s[i+p[i]]==s[i-p[i]]) p[i]++;
if(i+p[i]>mx) id=i,mx=i+p[i];
}
}
void calc(int op)
{
for(int i=1;i<=n;++i) hs[i]=hs[i-1]*P+s[i]-'a'+1;
manacher();
for(int i=1;i<=n;++i) val[i]=n;
for(int i=1;i<=n;++i) val[i+p[i]-1]=min(val[i+p[i]-1],i);
for(int i=n-1;i;--i) val[i]=min(val[i],val[i+1]);
for(int i=1;i<=n;++i)
{
f[op][i]=f[op][i-1]+(!mp[i-val[i]][geths(val[i],i)]);
mp[i-val[i]][geths(val[i],i)]=1;
}
for(int i=1;i<=n;++i) mp[i-val[i]].clear();
}
int m=256;
void getsa()
{
for(int i=1;i<=n;++i) t[rk[i]=s[i]]++;
for(int i=1;i<=m;++i) t[i]+=t[i-1];
for(int i=1;i<=n;++i) sa[t[rk[i]]--]=i;
for(int k=1;k<n;k<<=1)
{
int cnt=0;
for(int i=n-k+1;i<=n;++i) y[++cnt]=i;
for(int i=1;i<=n;++i) if(sa[i]>k) y[++cnt]=sa[i]-k;
for(int i=1;i<=m;++i) t[i]=0;
for(int i=1;i<=n;++i) t[rk[i]]++;
for(int i=1;i<=m;++i) t[i]+=t[i-1];
for(int i=n;i;--i) sa[t[rk[y[i]]]--]=y[i];
for(int i=1;i<=n;++i) y[i]=rk[i];
m=0;
for(int i=1;i<=n;++i) rk[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?m:++m;
if(m==n) break;
}
for(int i=1,j,k=0;i<=n;h[rk[i]]=k,++i)
for(k?--k:0,j=sa[rk[i]-1];s[j+k]==s[i+k];++k);
}
signed main()
{
n=rd();pw[0]=1;
for(int i=1;i<=n;++i) pw[i]=pw[i-1]*P;
scanf("%s",s+1);
getsa();
w[1]=1ll*n*(n+1)/2;
for(int i=1;i<=n;++i) w[1]-=h[i];
for(int i=1;i<=n;++i) pre[i]=i-1,suf[i]=i+1;
suf[n]=0;
for(int i=1;i<n;++i)
{
w[i+1]=w[i]-(n-i+1)+h[rk[i]];
if(suf[rk[i]])
{
w[i+1]+=h[suf[rk[i]]];
h[suf[rk[i]]]=min(h[suf[rk[i]]],h[rk[i]]);
w[i+1]-=h[suf[rk[i]]];
pre[suf[rk[i]]]=pre[rk[i]];
}
if(pre[rk[i]]) suf[pre[rk[i]]]=suf[rk[i]];
}
calc(0);
reverse(s+1,s+n+1);
calc(1);
reverse(f[1]+1,f[1]+n+1);
long long ans=0;
for(int i=1;i<n;++i)
{
ans=max(ans,f[0][i]*(w[i+1]-f[1][i+1]));
}
cout<<ans;
return 0;
}
浙公網(wǎng)安備 33010602011771號