AtCoder ABC 177 B – Substring Python解説

スポンサーリンク

Substring

2 つの文字列 S, T が与えられます。
T が S の部分文字列となるように、S のいくつかの文字を書き換えます。
少なくとも何文字書き換える必要がありますか?
ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。

AtCoder Beginner Contest 「Substring」

TがSの部分文字列になるための変更回数を求める問題です。方針としては、文字列Sの端から文字列Tの文字を重ねていき、変更に必要な文字数を求めて、その最小値を出力します。

s, t = input(), input()

ans = len(t)

for i in range(len(s) - len(t) + 1):
    cnt = 0
    for j in range(len(t)):
        if s[i+j] != t[j]:
            cnt += 1
    ans = min(ans, cnt)
    
print(ans)

まず、for文の外側のループはSの文字数 – Tの文字数 + 1回回します。
内側のループは、Tの文字数分ループを回し、s[i+j] != t[j]でSの文字とTの文字が一致するか調べています。s[i+j]とすることで、外側のfor文がループするたび、Sの文字を1文字ずつずらしています。

変更回数の最小値を求めたいので、ansに初期値としてTの文字数を入れ、あとはmin関数でansとcntを比較していきます。最後にansを出力して完了です。

AtCoderB問題

Posted by cheese