Z-Algorithm and Prefix Functions

A Z value measures prefix agreement from one position

z[i] is the length of the longest substring starting at i that matches the whole string's prefix. Maintain a previously matched interval to avoid repeating comparisons.

Copy codefun zValues(text: String): IntArray {
    val z = IntArray(text.length)
    var left = 0
    var right = 0
    for (i in 1 until text.length) {
        if (i < right) z[i] = minOf(right - i, z[i - left])
        while (i + z[i] < text.length && text[z[i]] == text[i + z[i]]) z[i]++
        if (i + z[i] > right) { left = i; right = i + z[i] }
    }
    return z
}

This uses a half-open matched interval [left,right) and sets z[0]=0 by convention. For "aaaa", it returns [0,3,2,1]. Prefix functions instead summarize borders ending at each position; both support linear-time pattern reasoning but store different information.

Exercise

Use Z values on pattern + separator + text to locate matches, ensuring the separator cannot occur in either input. Compare with a naive prefix-length calculation on short strings.

Check: when no unused character is guaranteed, use an integer encoding with a reserved sentinel instead of guessing a separator.

Further reading: Pattern matching