AtCoder Beginner Contest 177を見直すB - Substring

B - Substring

問題

文字列tと、tよりも長い文字列sが与えられるので、sの任意の文字を変更してsのなかにtを作る場合の最小変更数を答えよ。

例

s：cabacc
t：abc
>> 1

上記の場合、4文字目の「a」を「c」に入れ替え[cabccc]​とすることで「s」の中に「abc」を作ることができ、が変更数が１で最小となります。

解説をみて作成したコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
   string s, t;
   cin >> s >> t;
   int ans = t.size();
   rep(i, s.size()) {
       if(i + t.size() > s.size()) break;
       int cnt = 0;
       rep(j, t.size()) if(s[i + j] != t[j]) cnt++;
       ans = min(ans, cnt);
   }
   cout << ans << endl;
   return 0;
}

入力の文字列が1000文字なので、全検索で解答できます。文字列のsの頭から、sからtを引いた数まで、順にsとtの違いをカウントして最小値を確認しています。

解説みてみるとそんなに難しい問題じゃ無いんですが、当日には謎の考えに囚われて解答できなかったですね。残念