CF822B题解

· · 题解

题解思路：

枚举 t 的每一个字母作为开头，然后再和 s 比较，记录一下哪里不一样就要改，最后对这些修改的序列取长度最小的就可以了，长度一样的话，随便一个就可以了。

AC Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;
int n , m;
string a , b;
int main(){
    //freopen ("temp.in" , "r" , stdin);
    scanf ("%d%d" , &n , &m);
    cin >> a >> b;
    vector <int> ans(114514 , 1);//因为要取min，所以先把长度设成很大的值。
    for (int i = 0; i < m - n + 1; ++ i) {//枚举每一个t里的字母
        vector <int> temp;
        for (int j = 0; j < n; ++ j) 
            if (a[j] != b[i + j]) //只要不一样就要是 ？
                temp.push_back (j);//那么操作就加上j
        if (temp.size() < ans.size()) //更新答案
            ans = temp;
    }
    printf ("%d\n" , ans.size());
    for (int i = 0; i < ans.size(); ++ i)//输出
        printf ("%d " , ans[i] + 1);
    puts("");
    return 0;
}