Edit

【pythonでABC177を解説】B - Substring

問題概要

問題ページ

問題文

\(2\) つの文字列 \(S\), \(T\) が与えられます。

\(T\) が \(S\) の部分文字列となるように、\(S\) のいくつかの文字を書き換えます。

少なくとも何文字書き換える必要がありますか?

ただし、部分文字列とは連続する部分列のことを指します。例えば、xxxyxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。

制約

  • \(S,T\) は \(1\) 文字以上 \(1000\) 文字以下
  • \(T\) の長さは \(S\) の長さ以下
  • \(S,T\) は 英小文字のみを含む

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    t = str(input().rstrip('\n'))
    mn = len(t)
    for i in range(len(s) - len(t) + 1):
        t_mn = 0
        for j in range(len(t)):
            if s[i + j] != t[j]:
                t_mn += 1
        mn = min(mn, t_mn)
    print(mn)


if __name__ == '__main__':
    solve()

-Edit
-