String Matching Basics (Naive and Sliding Window)

Define matching boundaries before optimizing

Naive exact matching tries each valid start position and compares pattern characters. This version returns the first match, treats an empty pattern as matching at zero, and compares Kotlin Char units.

Copy codefun find(text: String, pattern: String): Int {
    if (pattern.isEmpty()) return 0
    if (pattern.length > text.length) return -1
    for (start in 0..text.length - pattern.length) {
        var offset = 0
        while (offset < pattern.length && text[start + offset] == pattern[offset]) offset++
        if (offset == pattern.length) return start
    }
    return -1
}

Worst-case work is O(nm), such as long repeated prefixes failing near each window's end. A sliding-window technique is especially useful when the property can be updated cheaply as one character enters and another leaves, such as fixed-length frequency counts.

Exercise

Test empty text, empty pattern, a longer pattern, overlapping matches, and no match. Extend the function to return all starts, defining empty-pattern behavior explicitly.

Check: case folding and Unicode normalization change matching semantics and indexes; they are separate policies, not automatic features of substring search.

Further reading: Substring search