Simple implementation of Knuth–Morris–Pratt algorithm

# ----------------------------------------------------------------------------

def build_kmp_table(input_buffer, pos, look_ahead_end):
    table = [-1]
    candidate = 0
    for i in range(1, look_ahead_end - pos):
        if input_buffer[pos + i] == input_buffer[pos + candidate]:
            table.append(table[candidate])
        else:
            table.append(candidate)
            while candidate >= 0 and (input_buffer[pos + i] != input_buffer[pos + candidate]):
                candidate = table[candidate]
        candidate += 1
    return table

# ----------------------------------------------------------------------------

def find_longest_match_kmp(input_buffer, sliding_window_start, pos, look_ahead_end):
    look_ahead_size = look_ahead_end - pos # Actual

    max_match_length = 0
    max_match_pos = 0

    table = build_kmp_table(input_buffer, pos, look_ahead_end)

    la_idx = 0 # k
    sw_idx = 0 # j

    while (sliding_window_start + sw_idx - la_idx) < pos:
        if input_buffer[pos + la_idx] == input_buffer[sliding_window_start + sw_idx]:
            la_idx += 1
            sw_idx += 1
            if la_idx == look_ahead_size:
                # Full-length match found, we're done
                max_match_pos = sliding_window_start + sw_idx - la_idx
                max_match_length = la_idx
                break
        else:
            if la_idx > max_match_length:
                max_match_pos = sliding_window_start + sw_idx - la_idx
                max_match_length = la_idx
            la_idx = table[la_idx]
            if la_idx < 0:
                la_idx += 1
                sw_idx += 1

    if max_match_length == 0:
        return 0, 0
    return (pos - max_match_pos, max_match_length)

# ----------------------------------------------------------------------------