What goes in the blank?
# KMP failure table: fail[i] = longest proper prefix
# of p[:i+1] that is also its suffix
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = fail[____]
if p[i] == p[k]:
k += 1
fail[i] = k
Answer: k - 1
On a mismatch, fall back to the next shorter border: the longest border of the current match p[:k], stored at fail[k - 1].
Play Problem Solving ▸