首页 > 代码库 > #422(div2)B. Crossword solving
#422(div2)B. Crossword solving
题意:给出2个字符串,A,B,A长度严格小于B长度,问改动A多少个字符,能成为B的子串,求最少改动
思路:暴力,2层FOR循环,可用set来存储已B的第i个字符为首需要改动的位置
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 set<int >a[1002]; 5 int main(){ 6 int n,m; 7 cin>>n>>m; 8 string s1,s2; 9 cin>>s1>>s2; 10 int l,sum; 11 int y; 12 int Max=1e9; 13 for(int i=0;i<=m-n;i++){ 14 l=i;sum=0; 15 16 for(int j=0;j<s1.size();j++){ 17 if(s1[j]!=s2[l++]) { 18 sum++; 19 20 a[i].insert(j+1); 21 } 22 } 23 24 if(sum<Max){ 25 Max=sum;y=i; 26 } 27 } 28 cout<<Max<<endl; 29 for(set<int >::iterator it=a[y].begin();it!=a[y].end();it++){ 30 printf("%d ",*it); 31 } 32 cout<<endl; 33 }
#422(div2)B. Crossword solving
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。