AtCoder Beginner Contest 177 [ B - Substring ] https://atcoder.jp/contests/abc177/tasks/abc177_b

abc177_b.py

'''
[問題]
https://atcoder.jp/contests/abc177/tasks/abc177_b

[解説]
https://atcoder.jp/contests/abc177/editorial/87
'''

import sys

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

S = input()
S = S.replace( '\n' , '' )

T = input()
T = T.replace( '\n' , '' )

ans = len(T)

# SとTを総当たりで見ていって、何文字違うかカウントする。その最小値が答え
for S_START in range(0, len(S) - len(T) + 1):

    diff = 0
    for i in range(0, len(T)):
        if S[S_START + i] != T[i]:
            diff += 1

    ans = min(ans, diff)

print(ans)