abc257G問題をKMP解法でACしているPythonコードがあまり見受けられなかったので、KMP解法で解いてみました。
誰かのお役に少しでも立てれば幸いです。
コード
"""
construct_mp(s) -> mp
mp[i] = s[0:x] = S[i-x:i]なる最大のx
例)
construct_mp(aba?ababaab) ->
[0, 0, 1, 0, 1, 2, 3, 2, 3, 1, 2]
"""
def construct_mp(S):
l = len(S)
ret = [0] * (l+1)
ret[0] = j = -1
for i in range(l):
while j >= 0 and S[i] != S[j]:
j = ret[j]
j += 1
ret[i+1] = j
return ret[1:]
s = input()
t = input()
mp = construct_mp(s + "?" + t)
ind = len(s) + len(t) #最右index
ans = 0
while ind > len(s): #Tが左端まで構成できていない限り
if mp[ind] == 0: #Tは作れない
ans = -1
break
ans += 1
ind -= mp[ind]
print(ans)
参考: https://snuke.hatenablog.com/entry/2014/12/01/235807 https://atcoder.jp/contests/abc257/editorial/4197
