KMP Algorithm (Prefix Table Concept)

Reuse the prefix already proved equal

KMP's prefix table records the longest proper prefix that is also a suffix for each pattern prefix. On mismatch, fall back to a shorter known border rather than rechecking text from the next starting position.

Copy codefun prefix(pattern: String): IntArray {
    val table = IntArray(pattern.length)
    for (i in 1 until pattern.length) {
        var length = table[i - 1]
        while (length > 0 && pattern[i] != pattern[length]) length = table[length - 1]
        if (pattern[i] == pattern[length]) length++
        table[i] = length
    }
    return table
}

For "ababaca", the table is [0,0,1,2,3,0,1]. During text scanning, apply the same fallback when a character disagrees; a matched length equal to the pattern length identifies a match. For all matches, fall back after reporting so overlaps remain discoverable.

Prefix construction and scanning are O(m+n), with O(m) table space.

Exercise

Implement the scanner and compare against naive matching on generated small strings. Test "aaaaa" with "aaa", which has starts zero, one, and two.

Check: handle an empty pattern before indexing it, and distinguish prefix-table conventions from failure tables that use a -1 sentinel.

Further reading: KMP