题解：CF822B Crossword solving

__DAN__ · 2025-01-12 14:03:40 · 题解

题目传送门

思路

因为此题样例较小，所以可以暴力，先求出不同的地方的个数，再跟最小值比较，如果小于最小值就更新。

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,m,as=1e9,sum;
string a,b;
int ans[1005];
int main(){
    cin>>n>>m>>a>>b;
    a="#"+a;
    b="#"+b;
    for(int i=1;i<=m-n+1;i++){
        int cnt=0;
        for(int j=1,k=i;j<=n;j++,k++)if(a[j]!=b[k])cnt++;
        if(as>cnt){
            as=cnt;
            memset(ans,0,sizeof ans);
            sum=0;
            for(int j=1,k=i;j<=n;j++,k++)if(a[j]!=b[k])ans[++sum]=j;
        }
    }
    cout<<as<<'\n';
    for(int i=1;i<=sum;i++)cout<<ans[i]<<' ';
    return 0;
}