$ ./guess_the_languageProblem Solving — fill the blank
Problem Solving — fill the blank · hard · #331

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 (also accepted: k - 1, 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 ▸