CodeForces 427D Match & Catch

2019-08-16 08:03:09来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

CodeForces 427D Match & Catch

洛谷题目页面传送门 & CodeForces题目页面传送门

给定\(2\)个字符串\(a,b,|a|=n,|b|=m\),求最长的既在\(a\)中出现恰好\(1\)次又在\(b\)中出现恰好\(1\)次的非空字符串的长度,如果不存在输出\(-1\)

\(n,m\in[1,5000]\)

emmm,数据范围很不友好,\(\mathrm O(nm)\)\(\log\)都不行。。。

考虑枚举\(a\)的子串。枚举子串可以转化为枚举所有后缀的所有前缀,这样一来就有了“前缀”这个东西可以利用。

我们在枚举\(a\)的后缀\(a_{i\sim n}\)的时候,令\(c=a_{i\sim n}+`\text{!'}+a+`\text{@'}+b,s=|c|\)。对\(c\)跑一遍Z算法(如果聪明的读者还不知道Z算法是什么,please点击这个),就可以知道后缀\(a_{i\sim n}\)\(a,b\)中的出现情况了。

我们先把\(z_{c,n-i+3\sim 2n-i+2},z_{c,2n-i+4\sim s}\)分别装在\(2\)个桶\(buc1,buc2\)里,即\(buc1_j\)表示使得从\(a\)的这个位置往后和\(a_{i\sim n}\)的前缀匹配最长长度为\(j\)的位置数,\(buc2\)类似。可是我们想要的是使得从\(a\)的这个位置往后和\(a_{i\sim n}\)的前缀匹配最长长度\(\bm{\ge j}\)的位置数,也就是使得从\(a\)的这个位置往后和\(a_{i\sim n}\)的前缀能够匹配\(\bm j\)这么长的位置数。于是我们可以从\(j=n-i+1\)\(j=1\)从大到小枚举即将被check的\(a_{i\sim n}\)的前缀的长度\(j\),每次若\(buc1_j=buc2_j=1\),则check成功,更新答案\(ans=\max(ans,j)\),然后令\(buc1_{j-1}=buc1_{j}+buc1_{j-1},buc2_{j-1}=buc2_{j}+buc2_{j-1}\)即可。考虑为什么这么从大到小递推是对的:首先\(buc1_{n-i+1},buc2_{n-i+1}\)本来就有我们想要的意思。每次更新\(buc1_{j-1},buc2_{j-1}\)都会把它们变成我们想要的意思下的值(感性理解理解),于是每到一个\(j\)\(buc1_j,buc2_j\)都会是我们想要的意思咯。(想一想就会发现,上述那个递推就是\([1,buc1_j/buc2_j]\)区间\(+1\)的差分。当然如果想不到差分的话,线段树或树状数组是比较容易想的,但是带\(\log\),过不掉。。。)

这样复杂度就是\(\mathrm O(n(n+m))\),侥幸过

下面考虑哈希怎么做。很显然是做不了的。。。最快也就是按上述方法,用哈希+二分求\(z\)数组,但数据范围不友好啊QWQ

对了,数据不清空,爆零两行泪。每枚举一个\(a\)的后缀时,都要清空\(2\)个桶!!!

下面上代码:

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=5000,M=5000;
int n,m,s;//|a|,|b|,|c| 
char a[N+5],b[M+5],c[2*N+M+5]/*a的后缀+'!'+a+'@'+b*/;
int z[2*N+M+1];//z数组 
void z_init(){//Z算法 
    int zl=0,zr=0;
    for(int i=2;i<=s;i++)
        if(zr<i){
            z[i]=0;
            while(i+z[i]<=s&&c[i+z[i]]==c[1+z[i]])z[i]++;
            if(z[i])zl=i,zr=i+z[i]-1;
        }
        else if(i+z[i-zl+1]<=zr)z[i]=z[i-zl+1];
        else{
            z[i]=zr-i+1;
            while(i+z[i]<=s&&c[i+z[i]]==c[1+z[i]])z[i]++;
            zl=i;zr=i+z[i]-1;
        }
//  cout<<"z";for(int i=2;i<=s;i++)cout<<z[i];puts("");
}
int buc1[N+1],buc2[N+1];//2个桶 
int main(){
    cin>>a+1>>b+1;
    n=strlen(a+1);m=strlen(b+1);
    int ans=inf; 
    for(int i=1;i<=n;i++){//枚举后缀的左端点 
        s=0;
        for(int j=i;j<=n;j++)c[++s]=a[j];
        c[++s]='!';
        for(int j=1;j<=n;j++)c[++s]=a[j];
        c[++s]='@';
        for(int j=1;j<=m;j++)c[++s]=b[j];
        c[s+1]=0;
        //上面都在造c 
//      cout<<c+1<<"\n";
        z_init();
        memset(buc1,0,sizeof(buc1));memset(buc2,0,sizeof(buc2));//数据不清空,爆零两行泪 
//      for(int j=n-i+3;j<=2*n-i+2;j++)cout<<c[j];cout<<" ";for(int j=2*n-i+4;j<=s;j++)cout<<c[j];puts("");
        for(int j=n-i+3;j<=2*n-i+2;j++)buc1[z[j]]++;//装到桶里面 
        for(int j=2*n-i+4;j<=s;j++)buc2[z[j]]++;//同上 
        for(int j=n-i+1;j;j--){//枚举后缀的前缀的长度 
//          printf("buc1[%d]=%d buc2[%d]=%d\n",j,buc1[j],j,buc2[j]);
            if(buc1[j]==1&&buc2[j]==1)ans=min(ans,j);//如果各出现恰好1次,则更新答案 
            buc1[j-1]+=buc1[j];buc2[j-1]+=buc2[j];//将buc1[j-1],buc2[j-1]变为我们想要的意思 
        }
//      puts("");
//      cout<<"ans="<<ans<<"\n";
    }
    printf("%d",ans<inf?ans:-1);
    return 0;
}

原文链接:https://www.cnblogs.com/ycx-akioi/p/CodeForces-427D.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:工作碰上的技术问题及处理经验(三)

下一篇:bozj1040: [ZJOI2008]骑士(奇环树,DP)