Java教程

hdu7015 / 2021“MINIEYE杯”中国大学生算法设计超级联赛(5)1004 Another String(尺取法+二阶差分)

本文主要是介绍hdu7015 / 2021“MINIEYE杯”中国大学生算法设计超级联赛(5)1004 Another String(尺取法+二阶差分),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

https://acm.hdu.edu.cn/showproblem.php?pid=7015

 

题意:

定义2个长度相等的字符串距离为对应位置不相同的字符个数

若两个字符串的距离<=k,则称他们是k相似的

给出一个字符串,将他分割为A[1,i]和B[i+1,n]两部分,

问从A、B中各选一个子串,有多少对满足是k相似的

对于i∈[1,n-1]依次回答

 

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

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

具体做法是枚举两个位置的间隔距离d

枚举i和j,i从1开始,j从i+d开始

若f[i][j]=L,那么f[i+1][j+1]就是L减去位置i和位置j的距离,再继续往后匹配

对于每个d,匹配的最后位置单调不减

 

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

枚举位置i和位置j,考虑以i和j为起始位置的字符串的贡献

设f[i][j]=x

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

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

如果分割位置在i+1,有2的贡献,即s[i]与s[j],s[i]s[i+1]与s[j]s[j+1]

如果分割位置在i+2,有3的贡献

……

直到分割位置在i+f[i][j]-1,有f[i][j]的贡献

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

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

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

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

0 0 0 1 2 3 ……f[i][j]-2 f[i][j]-1 f[i][j] f[i][j] f[i][j] 0 0 0

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

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

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

对于每一对i和j,在答案的二阶差分里只修改4个位置

i位置+1,i+f[i][j]位置-1,j位置-f[i][j],j+1位置+f[i][j]

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

 

小细节:

在求f[i][j]时,匹配位置可能超过n

在字符串的最后加一个特殊字符,然后限定匹配到n+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 T,n,m,dis,len,k;
    scanf("%d",&T);
    while(T--)
    {
        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]);
    }
}

 

这篇关于hdu7015 / 2021“MINIEYE杯”中国大学生算法设计超级联赛(5)1004 Another String(尺取法+二阶差分)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!