Codeforces Round #422 (Div. 2) B. Crossword solving 枚举
Erelong Leha was bored by calculating of the greatest common divisor of two factorials. Therefore he decided to solve some crosswords. It's well known that it is a very interesting occupation though it can be very difficult from time to time. In the course of solving one of the crosswords, Leha had to solve a simple task. You are able to do it too, aren't you?
Leha has two strings s and t. The hacker wants to change the string s at such way, that it can be found in t as a substring. All the changes should be the following: Leha chooses one position in the string s and replaces the symbol in this position with the question mark "?". The hacker is sure that the question mark in comparison can play the role of an arbitrary symbol. For example, if he gets strings="ab?b" as a result, it will appear in t="aabrbb" as a substring.
Guaranteed that the length of the string s doesn't exceed the length of the string t. Help the hacker to replace in s as few symbols as possible so that the result of the replacements can be found in t as a substring. The symbol "?" should be considered equal to any other symbol.
The first line contains two integers n and m (1 ≤ n ≤ m ≤ 1000) — the length of the string s and the length of the string tcorrespondingly.
The second line contains n lowercase English letters — string s.
The third line contains m lowercase English letters — string t.
In the first line print single integer k — the minimal number of symbols that need to be replaced.
In the second line print k distinct integers denoting the positions of symbols in the string s which need to be replaced. Print the positions in any order. If there are several solutions print any of them. The numbering of the positions begins from one.
3 5
abc
xaybz
2
2 3
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N = 1e3+, M = 1e3+,inf = 2e9; int n,m;
char s[N],t[N];
vector<int > G[N];
int main() {
scanf("%d%d",&n,&m);
scanf("%s%s",s+,t+);
int mi = inf;
for(int i = ; i <= m - n + ; ++i) {
for(int j = ; j <= n; ++j) {
if(s[j] != t[i+j-]) {
G[i].push_back(j);
}
}
mi = min(mi,(int)G[i].size());
}
for(int i = ; i <= m - n + ; ++i) {
if(G[i].size() == mi) {
cout<<mi<<endl;
for(int j = ; j < G[i].size(); ++j) {
cout<<G[i][j]<<" ";
}
return ;
}
}
return ;
}
最新文章
- Java api
- jquery------.resizable()的使用
- 夺命雷公狗---DEDECMS----33dedecms自定义搜索以及分页功能完成
- 优化Linux下的内核TCP参数来提高服务器负载能力
- A trip through the graphics pipeline 2011 Part 10(翻译)
- C# Socket 入门1(转)
- RAD XE10 Seattle
- POJ 3204 Ikki's Story I-Road Reconstruction (网络流关键边)
- 28个MongoDB NoSQL数据库的面试问答
- 1066. Root of AVL Tree
- highcharts-Highmaps 动态传入城市名称
- Eclipse中输入系统变量和运行参数--转
- ERROR 1 (HY000): Can&#39;t create/write to file &#39;/tmp/#sql_909_0.MYI&#39; (Errcode: 13)
- Windows Server 2016-Telnet 简介及安装
- MVC Web.Config 配置错误
- JqGrid分页按钮图标不显示的bug
- SpringMVC学习 十三 拦截器栈
- qt无法使用终端启动的解决方法
- ctype
- Django之路由控制配置