cf 822B Crossword solving
1 second
256 megabytes
standard input
standard output
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 string s="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 t correspondingly.
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
4 10
abcd
ebceabazcd
1
2 暴力搜素 n*m复杂度
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define lowbit(x) x&(-x)
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define mem(a) (memset(a,0,sizeof(a)))
const int inf=0x3f3f3f3f;
int main()
{
int n,m,maxn=,c=,id;
string s,t;
cin>>n>>m>>s>>t;
for(int i=;i<=m-n;i++)
{
c=;
for(int j=;j<n;j++)
{
if(t[i+j]!=s[j]) c++;//每次循环判断最少不匹配的个数。
}
if(c<maxn)
{
maxn=c;
id=i;
}
}
if(maxn==) printf("0\n"),;
else printf("%d\n",maxn);
for(int i=;i<n;i++)
{
if(t[id+i]!=s[i])
printf("%d ",i+);
}
return ;
}
最新文章
- C++网络编程之select
- PLSQL Developer 不能连接 oracle 11g 64位 的解决办法
- 【bzoj2631】tree link-cut-tree
- js只允许输入数字
- SqlServer和MySQL游标学习
- swift实现冒泡排序
- linux percona-toolkit的安装
- Qtwebkit flashplayer插件问题
- JDK动态代理例子
- js比量undefined种类
- HDOJ 5000 Clone
- rabbitmq-message(C#)
- 在Centos中yum安装和卸载软件的使用方法
- IntelliJ IDEA运行项目成功后,无法访问Tomcat主页
- 【转】JAVA异常报错大全
- OpenCV设置摄像头分辨率及全屏显示
- [Z] SQL SERVER 的前世今生--各版本功能对比
- spring boot(十四)shiro登录认证与权限管理
- 【跟着开涛学Shiro】(一)Shiro简介
- How to Install and Configure Bind 9 (DNS Server) on Ubuntu / Debian System
热门文章
- CAD二次开发(01)-绘制直线
- windos环境python3.5安装 paramiko
- VMware 下扩展linux硬盘空间
- C++ double转string类型以及MFC控件简单使用方法
- &;lt;&;lt;Python基础教程&;gt;&;gt;学习笔记 | 第12章 | 图形用户界面
- Mongodb集群之副本集
- dig linux下的使用
- Git-如何将已存在的项目提交到git
- centos 服务器配置注意项
- 用jquery给select加选中事件