首页 > 代码库 > Codeforces Round #422 B
Codeforces Round #422 B
Crossword solving
题意:给2个字符串s1,s2,求至少改变s2的多少个字符,才能使s2中包含s1,并输出改变的位置
思路:暴力枚举以每一个位置为开始,和s2匹配,求答案
AC代码:
#include<bits/stdc++.h> #include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #define ll long long #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a) memset(a,0,sizeof(a)) #define mp(x,y) make_pair(x,y) #define pb push_back const long long INF = 1e18+1LL; const int inf = 1e9+1e8; using namespace std; const int N=1e5+100; char a[1005],b[1005]; int anss[1005]; int ans=100005,la,lb; int main(){ cin>>la>>lb; cin>>a+1>>b+1; for(int i=0; i<=lb-la; ++i){ int k=0; for(int j=1; j<=la; ++j){ if(a[j]!=b[j+i]) k++; } if(k<ans){ int l=0; for(int j=1; j<=la; ++j){ if(a[j]!=b[j+i]){ anss[++l]=j; } } ans=k; } } cout<<ans<<endl; for(int i=1; i<=ans; ++i){ cout<<anss[i]<<‘ ‘; } return 0; }
Codeforces Round #422 B
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。