from typing import List


def build_lps_table(prefix: str) -> List[int]:
    """Build the LPS table for the KMP algorithm. This table specifies whether
    the current character is part of an earlier prefix, so we know the latest
    character to check for when we are scanning the string. The table
    preprocesses the pattern and looks for the longest prefix that is also a
    suffix, which means that we can use this table rather than backtrack when
    scanning the string to see if it contains the pattern.

    Note that this function takes the pattern rather than the input string.

    This function is O(n) time and space, where n is `len(prefix)`.
    """
    if len(prefix) == 0:
        return []
    table = [0] * len(prefix)

    # The current index in the preprocessing table
    i = 1

    # The next character of the candidate substring
    cand = 0

    # Base case
    table[0] = -1

    for i in range(1, len(prefix)):
        if prefix[i] == prefix[cand]:
            table[i] = table[cand]
        else:
            table[i] = cand
            cand = table[cand]

            while cand >= 0 and prefix[i] != prefix[cand]:
                cand = table[cand]
        cand += 1
    return table