def kmp(S):
    """Runs the Knuth-Morris-Pratt algorithm on S.

    Returns a table F such that F[i] is the longest proper suffix of S[0...i]
    that is also a prefix of S[0...i].
    """
    n = len(S)

    if n == 0:
        return []

    F = [0] * n

    for i in range(1, n):
        k = F[i - 1]

        while k > 0 and S[k] != S[i]:
            k = F[k - 1]

        if S[k] == S[i]:
            k += 1

        F[i] = k

    return F