問題概要
問題ページ
-
-
B - Substring
問題ページへ移動する
問題文
\(2\) つの文字列 \(S\), \(T\) が与えられます。
\(T\) が \(S\) の部分文字列となるように、\(S\) のいくつかの文字を書き換えます。
少なくとも何文字書き換える必要がありますか？
ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、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()