1 条题解

  • 0
    @ 2026-11-15 17:07:47

    题目分析

    令 f[i][j]f[i][j] 表示从字符串的 ii 位置和 jj 位置开始,能够满足 kk 相似的最长长度。

    可以用尺取法在 O(n2)O(n^2) 的复杂度中求出来。

    具体做法是:

    • 枚举两个位置的间隔距离 dd;
    • 枚举 ii 和 jj,ii 从 11 开始,jj 从 i+di+d 开始;
    • 若 f[i][j]=Lf[i][j]=L,那么 f[i+1][j+1]f[i+1][j+1] 就是 LL 减去位置 ii 和位置 jj 的距离,再继续往后匹配;
    • 对于每个 dd,匹配的最后位置单调不减。

    设 ans[i]ans[i] 表示在 ii 后面分割,能找出的 kk 相似字符串对数。

    枚举位置 ii 和位置 jj,考虑以 ii 和 jj 为起始位置的字符串的贡献。

    设 f[i][j]=xf[i][j]=x。

    也就是说 s[i]=s[j],s[i+1]=s[j+1]s[i]=s[j],s[i+1]=s[j+1],……,s[i+x−1]=s[j+x−1]s[i+x-1]=s[j+x-1]。

    所以如果分割位置在 ii,以 ii 和 jj 为起始位置的字符串会有 11 的贡献,即 s[i]s[i] 与 s[j]s[j]。

    • 如果分割位置在 i+1i+1,有 22 的贡献,即 s[i]s[i] 与 s[j]s[j],s[i]s[i+1]s[i]s[i+1] 与 s[j]s[j+1]s[j]s[j+1];
    • 如果分割位置在 i+2i+2,有 33 的贡献。
    • ……
    • 直到分割位置在 i+f[i][j]−1i+f[i][j]-1,有 f[i][j]f[i][j] 的贡献。

    当分割位置在 i+f[i][j]−1i+f[i][j]-1 后面且在 jj 前面,都是有 f[i][j]f[i][j] 的贡献。

    当分割位置在 jj 后面,因为要求分割位置左右各选一个子串,所以无贡献。

    另外,jj 不能超过分割位置,所以 f[i][j]f[i][j] 与 j−ij-i 取小。

    我们看以 ii 和 jj 为起始位置的字符串对不同的分割位置产生的贡献:

    $0,0,0,1,2,3,\ldots,f[i][j]-2,f[i][j]-1,f[i][j],f[i][j],f[i][j],0,0,0$。

    最前面的 11 是从分割位置 ii 开始的,到分割位置 i+f[i][j]−1i+f[i][j]-1 贡献依次加 11,然后从分割位置 i+f[i][j]i+f[i][j] 开始贡献都是 f[i][j]f[i][j] 不变,再从分割位置 jj 后贡献都是 00。

    对这个贡献做一次差分得到 0,0,0,1,1,10,0,0,1,1,1 …… 1,1,1,0,0,−f[i][j],0,01,1,1,0,0,-f[i][j],0,0。

    再做一次差分得到二阶差分 0,0,0,1,0,00,0,0,1,0,0 …… 0,0,0,−1,0,−f[i][j],f[i][j],00,0,0,-1,0,-f[i][j],f[i][j],0。

    对于每一对 ii 和 jj,在答案的二阶差分里只修改 44 个位置。

    ii 位置 +1+1,i+f[i][j]i+f[i][j] 位置 −1-1,jj 位置 −f[i][j]-f[i][j],j+1j+1 位置 +f[i][j]+f[i][j]。

    最后求两次前缀和还原答案序列。

    小细节:在求 f[i][j]f[i][j] 时,匹配位置可能超过 nn。

    在字符串的最后加一个特殊字符,然后限定匹配到 n+1n+1,因为程序写法是到不合法位置停止。

    #include<bits/stdc++.h>
    
    using namespace std;
    
    #define N 3002
    
    char s[N];
    int f[N][N];
    
    long long ans[N];
    
    int main()
    {
        int n,m,dis,len,k;
        scanf("%d%d",&n,&m);
        scanf("%s",s+1);
        for(int i=1;i<=n;++i)
            for(int j=i+1;j<=n;++j)
                f[i][j]=0;
        for(int i=1;i<n;++i) ans[i]=0;
        s[n+1]='#';
        for(int d=1;d<n;++d)
        {
            dis=0;
            len=0;
            for(int i=1,j=i+d;j<=n;++i,++j)
            {
                while(dis<=m && j+len<=n+1)
                {
                    dis+=s[i+len]!=s[j+len];
                    ++len;
                }
                f[i][j]=len-1;
                dis-=s[i]!=s[j];
                len--;
            }
        }
        for(int i=1;i<=n;++i)
            for(int j=i+1;j<=n;++j)
            {
                ans[i]++;
                k=min(j-i,f[i][j]);
                ans[i+k]--;
                ans[j]-=k;
                ans[j+1]+=k;
            }
        for(int i=2;i<n;++i) ans[i]+=ans[i-1];
        for(int i=2;i<n;++i) ans[i]+=ans[i-1];
        for(int i=1;i<n;++i) printf("%lld\n",ans[i]);
        return 0;
    }
    • 1

    信息

    ID
    148
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    2
    已通过
    1
    上传者