ABC138 E - Strings of Impurity

問題原文

atcoder.jp

問題要旨

文字列 と文字列 が与えられる。
を 回繰り返した文字列において、何文字目までを使えば部分文字列として と同じものをとりうるか？　　 どう頑張っても取り得ない場合は -1 を出力せよ。

• 
• は英子文字からなる。

解法

まず、 にあって にないようなものがある場合、どう頑張っても不可能。
そうでない場合には、 をとんでもない回数繰り返すので、どこかでは作ることができる。

は長くなったりしないのがポイントで、 を前からなめながら「何文字目まで見たらいいか？ 」を更新していく。
これは、あらかじめ の各文字の出現場所をメモっておいて、二分探索で目的の文字の次の出現場所を探すようにするとできる。
（例えば、 a を探すとして、 内の a の出現場所が[3, 6, 9]であって、今7文字目まで見ていることになっている場合、次の出現場所は9。すでに9文字目以降を見てしまっている場合には、もう一周しないと a は見つからないので、 をもう一回繰り返した上で、3文字目まで見ていることにする。）

実装

注意点は２つ。

1. bisect_left でなく、 bisect_right を使う。
   bisect_left だと、同じ文字が連続するような場所で、ある１つの出現場所を使いまわしてしまう。

2. 最初の「どこまで見たか」の値は０より小さい値にする。
   ０だと bisect_right を使った場合に最初の出現場所を飛ばしてしまうことがある。
   出現場所のindexの記録方法を1-indexedにすることでも解決できる。

あとサンプルだけなまじ通る場合があるので、 , などで実験すると吉。（これの答えは6になります）

from collections import defaultdict
from bisect import bisect_right
S = input()
T = input()
NS = len(S)

# 構成不可
if set(list(T)) - set(list(S)):
    print(-1)
    exit()


# 各文字の出現場所を記録
D = defaultdict(list)
for i, s in enumerate(S):
    D[s].append(i)


ans = 0
marker = -1
for t in T:
    target_char_appeared_indexes = D[t]
    bi = bisect_right(target_char_appeared_indexes, marker)
    # もう一周してこないと見つけられない
    if bi == len(target_char_appeared_indexes):
        ans += NS
        marker = target_char_appeared_indexes[0]
    else:
        marker = target_char_appeared_indexes[bi]


# 0-indexedのため+1
print(ans + marker + 1)

感想

あぁ〜〜〜〜〜〜〜こういう実装が瞬殺できると気持ちいいんじゃぁ〜〜〜〜〜〜〜〜〜〜＾＾（１WAの顔）
個人的に結構好きな問題の一つ。実装が心地いい。自分で強いサンプルを準備しようね！