题解 P3649 【[APIO2014]回文串】
xtx1092515503
2020-07-27 20:50:51
# [Portal](https://www.luogu.com.cn/problem/P3649)
这里介绍一种**全新的后缀数组解法**。
定义：$sa$、$rk$、$ht$数组，即为SA里的常规数组。
我们依旧求出$ht$数组，并利用**单调栈**（可以参见[[AHOI2013]差异](https://www.luogu.com.cn/problem/P4248)的题解或者本人的[后缀数据结构学习笔记](https://www.luogu.com.cn/blog/Troverld/hou-zhui-shuo-ju-jie-gou-xue-xi-bi-ji)）求出每个位置最多可以向左向右分别延伸到多远。即，$(L_i,R_i)$为满足$(\min\limits_{j=L_i+1}^{R_i-1}ht_j)\geq ht_i$的最大区间。则串$s[sa_i,\dots,sa_i+ht_i-1]$共出现了$R_i-L_i$次。
这里是求出$(L_i,R_i)$的代码:
```cpp
L[0]=stk[0]=1;
for(int i=2;i<=n;i++){
while(tp&&ht[stk[tp]]>ht[i])R[stk[tp--]]=i;
if(ht[stk[tp]]==ht[i])L[i]=L[stk[tp]];
else L[i]=stk[tp];
stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n+1;
```
（事实上，我们求出这个数组的目的，就是为了得到$R_i-L_i$，即它的出现次数）
然后，对于每个$i$，我们**HASH+二分**出来$s[sa_i,\dots,sa_i+ht_i-1]$的**前缀**中，最长的**回文串**长度。则（长度*出现次数），即可与答案取$\max$。
这里我们先解答几个问题：
Q1：为什么一定要是**前缀回文串**？$s[sa_i,\dots,sa_i+ht_i-1]$的任何子串不都出现了$R_i-L_i$次吗？
A1:确实，这里是应该用它的全部子串。但是，我们不要忘记，它的每个子串，都是**某一条后缀的前缀**！所以，总有一条后缀，会计算它的非前缀子串的。并且，在这里计算的话，它出现的次数也会少于它真实的出现次数，毕竟这里是要求$s[sa_i,\dots,sa_i+ht_i-1]$这**一整个字符串**全都出现，但是如果只讨论该字符串的子串的话，出现次数也会更多。
Q2：那既然讨论子串时次数会更多，为什么要在这里讨论它的前缀呢？说不定它的前缀的出现次数也会更多呢？
A2：确实，它的次数确实会更多。我们把前缀的合法区间设为$(L',R')$，则必有$(L_i,R_i)\subset(L',R')$。但是，我们设$(L',R')$中$\min$的位置为$p$，则必有$(L_p,R_p)=(L',R')$！因此，这个前缀的贡献，会在$p$处被计算，在那时的$(L_p,R_p)$即是它真实的出现次数。
这里是二分+HASH的写法：
```cpp
for(int i=2;i<=n;i++){
int tms=R[i]-L[i];
int l=0,r=ht[i];
while(l<r){
int mid=(l+r+1)>>1;
if((pre[sa[i]+mid-1]-pre[sa[i]-1])==(suf[sa[i]+ht[i]-mid]-suf[sa[i]+ht[i]]))l=mid;
else r=mid-1;
}
res=max(res,1ll*tms*l);
}
```
当然，以某个位置开头的最长回文串长度，是可以使用Manacher$O(1)$求出的，这里因为~~懒得推了~~就使用HASH吧。
但是，如果你带入第一组样例算的话，会发现算出来的结果是$6$，而非$7$。
为什么呢？
因为所有只出现一次的回文串都不会被统计上！
所以我们只需再跑一遍Manacher求回文串最大长度即可。不会的可以参见本人的[Manacher感性瞎扯](https://www.luogu.com.cn/blog/Troverld/manacher-gan-xing-xia-che)。
复杂度$O(n\log n)$。
代码（~~SA+HASH+Manacher模板三合一，你值得拥有~~）：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int x[400100],y[400100],sa[400100],ht[400100],rk[400100],buc[400100],n,m;
int L[400100],R[400100],stk[400100],tp;
char s[400100],str[800100];
ll res;
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<=n)^(b+k<=n))return false;
if((a+k<=n)&&(b+k<=n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=1;i<=m;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[sa[1]]=num=1;
for(int i=2;i<=n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=1;i<=n;i++)rk[sa[i]]=i;
for(int i=1,k=0;i<=n;i++){
if(rk[i]==1)continue;
if(k)k--;
int j=sa[rk[i]-1];
while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k])k++;
ht[rk[i]]=k;
}
}
typedef unsigned long long ull;
ull sd1=998244353,sd2=666623333,pov1[401000],pov2[401000];
struct HASH{
ull val1,val2;
int len;
HASH(){
val1=val2=0ull;
len=0;
}
HASH(char ip){
val1=val2=ip;
len=1;
}
friend HASH operator +(const HASH &x,const HASH &y){
HASH z;
z.val1=x.val1*pov1[y.len]+y.val1;
z.val2=x.val2*pov2[y.len]+y.val2;
z.len=x.len+y.len;
return z;
}
friend HASH operator -(const HASH &x,const HASH &y){
HASH z;
z.val1=x.val1-y.val1*pov1[x.len-y.len];
z.val2=x.val2-y.val2*pov2[x.len-y.len];
z.len=x.len-y.len;
return z;
}
friend bool operator ==(const HASH &x,const HASH &y){
if(x.len!=y.len)return false;
if(x.val1!=y.val1)return false;
if(x.val2!=y.val2)return false;
return true;
}
}pre[401000],suf[800100];
int Centre,Rpos,rad[800100],S;
void prep(){
str[S++]='#';
for(int i=1;i<=n;i++)str[S++]=s[i],str[S++]='#';
}
void Manacher(){
Centre=Rpos=-1;
for(register int i=0;i<S;i++){
rad[i]=(i<Rpos)?min(Rpos-i,rad[Centre*2-i]):1;
while(i+rad[i]<S&&i-rad[i]>=0)if(str[i+rad[i]]==str[i-rad[i]])rad[i]++;else break;
if(i+rad[i]>Rpos)Rpos=i+rad[i],Centre=i;
res=max(res,1ll*rad[i]-1);
}
}
int main(){
scanf("%s",s+1),n=strlen(s+1),m='z',pov1[0]=pov2[0]=1;
for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+HASH(s[i]);
for(int i=n;i>=1;i--)suf[i]=suf[i+1]+HASH(s[i]);
SA();
// for(int i=1;i<=n;i++)printf("%d ",rk[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",ht[i]);puts("");
L[0]=stk[0]=1;
for(int i=2;i<=n;i++){
while(tp&&ht[stk[tp]]>ht[i])R[stk[tp--]]=i;
if(ht[stk[tp]]==ht[i])L[i]=L[stk[tp]];
else L[i]=stk[tp];
stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n+1;
for(int i=2;i<=n;i++){
int tms=R[i]-L[i];
int l=0,r=ht[i];
while(l<r){
int mid=(l+r+1)>>1;
if((pre[sa[i]+mid-1]-pre[sa[i]-1])==(suf[sa[i]+ht[i]-mid]-suf[sa[i]+ht[i]]))l=mid;
else r=mid-1;
}
res=max(res,1ll*tms*l);
}
prep();
Manacher();
// for(int i=0;i<S;i++)printf("%c ",str[i]);puts("");
// for(int i=0;i<S;i++)printf("%d ",rad[i]);puts("");
printf("%lld\n",res);
return 0;
}
```