Codeforces Round #422 (Div. 2)

http://codeforces.com/contest/822/problem/B

题意：在S1中改变最少次数使得在S2中可以找到S1； 枚举左端点，暴力寻找cnt最小值，复杂度O(n*(m-n+1)) ,n,n<=1000

#include <stdio.h>

#include <iostream>
#define MAXN 1000+5
using namespace std;
int main(void)
{
int n,m;
cin >> n >> m;
char s1[MAXN],s2[MAXN];
scanf("%s%s",s1+1,s2+1);
//printf("%s\n%s",s1,s2);
int cnt=n;
int index;
int i,j;
for(i=1;i<=m-n+1;i++)
{
int cnt1=0;
int t=i;
for(j=1;j<=n;j++,t++)
{
if(s2[t]!=s1[j]) cnt1++;
}
if(cnt1<cnt)
{
cnt=cnt1;
index=i;
}
//printf("%d--%d--%d -- ",cnt,index,i);
}
printf("%d\n",cnt);
int t=index;
for(int i=1;i<=n;i++,t++)
{
if(s1[i]!=s2[t])
{
if(cnt==1)
{
printf("%d",i);
cnt--;
}
else
{
printf("%d ",i);
cnt--;
}
}
}
}