首页 > 代码库 > LYDSYday1 String Master

LYDSYday1 String Master

技术分享

技术分享

/*暴力枚举两个后缀,计算最长能匹配多少前缀。最优策略一定是贪心改掉前 k 个失配的字符。时间复杂度 O(n3)。*/#include<cstdio>int n,m,i,j,k,x,y,ans;char a[310],b[310];int main(){  freopen("master.in","r",stdin);freopen("master.out","w",stdout);  scanf("%d%d%s%s",&n,&m,a+1,b+1);  for(i=1;i<=n;i++)for(j=1;j<=n;j++)    for(x=i,y=j,k=0;x<=n&&y<=n;x++,y++){      if(a[x]!=b[y]){        k++;        if(k>m)break;      }      if(ans<x-i+1)ans=x-i+1;    }  printf("%d",ans);  fclose(stdin);fclose(stdout);  return 0;}

 

LYDSYday1 String Master