BZOJ4962 : 简单的字符串

时间:2022-08-07 16:42:50

枚举子串的中心,往两侧扩展,将两侧对应位置的字符交替写下来,得到一个字符串$S$。

若前后长度为$L$的子串循环同构,则在$S$中它们对应长度为$2L$的前缀,需要满足它可以由不超过$2$个偶回文串拼接而成。

有一个结论是,若$S=uv$,其中$uv$都是偶回文串,那么要么$u$是$S$的最长偶回文前缀,要么$v$是$S$的最长偶回文后缀。

证明:

设$S=x_1y_1=x_2y_2=x_3y_3$。

假设结论不成立,那么显然双回文划分数$\geq 3$,设$x_1$为$S$的最长回文前缀,$y_3$是$S$的最长回文后缀,$x_2$和$y_2$都是回文串,则$y_1$和$x_3$都不是回文串。

因为$x_1$是最长回文前缀,所以$|x_1|>|x_2|$,同理$|y_2|<|y_3|$,则$|x_1|>|x_2|>|x_3|$。

................[v.....]

[x1...................][y1....]

[x2..........][y2.............]

[x3.....][y3..................]

设$x_1=x_2v$,那么因为$v$是回文串$y_2$的前缀,所以$v^R$是$y_2$的后缀,也是$y_3$的后缀,因为$y_3$是回文串,所以$v$是$y_3$的前缀,得出$x_3v$是$x_1$的前缀。

因为$x_1$是回文串,$x_2$是$x_1$的前缀,所以$x_2^R$是$x_1$的后缀,又因为$x_2$是回文串,所以$x_2$也是$x_1$的后缀,所以长度$|x_1|-|x_2|=|v|$是$x_1$的一个周期,也是$x_1$的前缀$x_3v$的一个周期。这说明$|v|$也是$v^Rx_3^R$的一个周期,即$x_3^R$是$v^Rv^R...v^Rv^R$的前缀。

因为$v$是回文串$x_1$的后缀,所以$v^R$是$x_1$的前缀,而$|v|$是$x_1$的周期,所以$x_1$是$v^Rv^R...v^Rv^R$的前缀,那么$x_1$的前缀$x_3$也是$v^Rv^R...v^Rv^R$的前缀。

因为$x_3^R$和$x_3$都是$v^Rv^R...v^Rv^R$的前缀,所以$x_3=x_3^R$,即$x_3$是回文串,和假设矛盾。所以结论成立。

通过Manacher预处理出每个位置的最长回文半径$f$,即可求出每个前缀的最长偶回文前缀和最长偶回文后缀,剩下部分可以根据$f$数组$O(1)$判断一个子串是否是回文串。

时间复杂度$O(n^2)$。

#include<cstdio>
const int N=10010;
int n,i,a[N],c[N],s[N],f[N],pre[N],suf[N],ans;
inline int min(int a,int b){return a<b?a:b;}
inline void umin(int&a,int b){a>b?(a=b):0;}
inline void umax(int&a,int b){a<b?(a=b):0;}
inline bool check(int l,int r){
if(l>r)return 1;
return l+r+f[l+r]>r+r;
}
inline void solve(int x){
int i,j,r,p,m=0,len;
for(i=x,j=x+1;i&&j<=n;i--,j++)c[++m]=a[i],c[++m]=a[j];
for(i=1;i<=m;i++)s[i<<1]=c[i],s[i<<1|1]=-1;
s[0]=-2,s[1]=-1,s[len=(m+1)<<1]=-3;
for(r=p=0,f[1]=1,i=2;i<len;i++){
for(f[i]=r>i?min(r-i,f[p*2-i]):1;s[i-f[i]]==s[i+f[i]];f[i]++);
if(i+f[i]>r)r=i+f[i],p=i;
}
for(i=0;i<=m+1;i++)pre[i]=0,suf[i]=len;
for(i=3;i<len;i+=2){
if(f[i]==i)pre[f[i]-1]=f[i]-1;
umin(suf[(i+f[i]-1)>>1],i>>1);
}
for(i=1;i<=m;i++)umax(pre[i],pre[i-1]);
for(i=m;i;i--)umin(suf[i],suf[i+1]);
for(i=0;i<=m;i++)if(suf[i]>=i)suf[i]=0;else suf[i]=(i-suf[i])<<1;
for(i=2;i<=m;i+=2)if(check(pre[i]+1,i)||check(1,i-suf[i]))ans++;
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<n;i++)solve(i);
return printf("%d",ans),0;
}