首页 > 其他 > 详细

LYDSYday1 String Master

时间:2016-10-03 00:12:47      阅读:135      评论:0      收藏:0      [点我收藏+]

技术分享

技术分享

/*
暴力枚举两个后缀,计算最长能匹配多少前缀。
最优策略一定是贪心改掉前 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

原文:http://www.cnblogs.com/hyfer/p/5928200.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!