CF961F

Miraik · 2022-11-21 16:51:18 · 题解

简要题意

给一个长度为 n 的字符串 s，对于 1 \le k \le \lceil \frac{n}{2} \rceil 求 s[k,n-k+1] 的 最长且长度为奇数 的 \text{border} 的长度。

题解

注意到一个惊人的事实：对于所有 k，我们要求解的子串的中心位置相同。

因此我们发现，如果我们从中间向两边扩展，即 k 从大到小做，必然有 ans_i \le ans_{i+1}+2。

证明很简单，就相当于你往两边各插入一个字符，那么 \text{border} 长度最多增加 2（也就是当前的 \text{border} 继续匹配掉这两个字符）。

那我们只需要在 k 从大往小做的时候先将当前 \text{border} 长度加 2，然后直接用字符串哈希判断一下 \text{border} 是否合法，不合法就不停减 2 就好了。

由于每次 \text{border} 长度最多增加 2，那么我们整个流程中 \text{border} 长度减小的次数也最多为 n，因此时间复杂度就是线性的了。

代码非常简短。

#include<cstdio>
const int N=1000005;
const int mod=1000000007;
int n,m,pw[N],hsh[N],f[N],ans; char s[N];
inline int gethash(int l,int r){
    int k=r-l+1;
    return (hsh[r]+mod-1ll*pw[k]*hsh[l-1]%mod)%mod;
}
main(){
    scanf("%d%s",&n,s+1); m=(n-1)/2;
    pw[0]=1; for(int i=1;i<=n;i++) pw[i]=pw[i-1]*131ll%mod;
    for(int i=1;i<=n;i++) hsh[i]=(hsh[i-1]*131ll+s[i]-'a')%mod;
    f[m+1]=-1;
    for(int i=m;~i;i--){
        f[i]=f[i+1]+2;
        while(~f[i] && i*2+f[i]>=n) f[i]-=2;
        while(~f[i] && gethash(i+1,i+f[i]) != gethash(n-i-f[i]+1,n-i) ) f[i]-=2;
    }
    for(int i=0;i<=m;i++) printf("%d%c",f[i],i==(n-1)/2?'\n':' ');
}