String Searching Algorithms

Welcome to this insightful lesson. Today's focus will be on string searching algorithms, a fundamental part of programming, often encountered in software development, the design of databases, and information retrieval. This lesson will walk you through the intricacies of these algorithms, explaining the principles behind each one.

For instance, if we consider the KMP string searching algorithm, the essence of its design is to eliminate the need to backtrack by retaining the information elicited from previous comparisons. If, at some point in the pattern, there's a mismatch, the algorithm does not begin matching from the start, but from a pre-computed point using a Longest Prefix Suffix (LPS) array.

Here is a concise KMP implementation in Kotlin:

fun kmpSearch(text: String, pattern: String): Int {
    if (pattern.isEmpty()) return 0
    
    fun computeLPS(pattern: String): IntArray {
        val lps = IntArray(pattern.length)
        var length = 0
        var i = 1
        while (i < pattern.length) {
            if (pattern[i] == pattern[length]) {
                lps[i++] = ++length
            } else {
                if (length != 0) length = lps[length - 1] else lps[i++] = 0
            }
        }
        return lps
    }
    
    val lps = computeLPS(pattern)
    var i = 0 // text index
    var j = 0 // pattern index
    
    while (i < text.length) {
        if (pattern[j] == text[i]) {
            i++; j++
        }
        if (j == pattern.length) return i - j
        else if (i < text.length && pattern[j] != text[i]) {
            if (j != 0) j = lps[j - 1] else i++
        }
    }
    return -1
}

The KMP algorithm operates with a time complexity of $O(n + m)$, where $n$ is the length of the text and $m$ is the length of the pattern. This efficiency is achieved because the algorithm never backtracks the text index i. The space complexity is $O(m)$ due to the storage required for the LPS array.

Another powerful approach is the Rabin-Karp algorithm, which uses hashing to find patterns. Instead of comparing characters directly, it computes a numerical hash for the pattern and compares it against the hash of every "window" in the text.

To make this efficient, we use a Rolling Hash. When the window slides one position to the right, we don't recompute the hash from scratch. Instead, we:

1. Remove the contribution of the character leaving the window.
2. Shift the remaining hash value (usually by multiplying by a base radix).
3. Add the contribution of the new character entering the window.

This "rolling" mechanism allows us to update the hash in $O(1)$ time, enabling the search to run in $O(n + m)$ average time. However, in the worst case (many hash collisions), it can degrade to $O(n \times m)$.

Here is how you can implement Rabin-Karp in Kotlin:

fun rabinKarpSearch(text: String, pattern: String): Int {
    val n = text.length
    val m = pattern.length
    if (m == 0) return 0
    if (n < m) return -1

    val d = 256 // Number of characters in the input alphabet
    val q = 101 // A prime number for modulo operations
    var h = 1
    var p = 0 // Hash value for pattern
    var t = 0 // Hash value for text window

    // The value of h would be "pow(d, m-1) % q"
    repeat(m - 1) {
        h = (h * d) % q
    }

    // Calculate the initial hash value of pattern and first window of text
    for (i in 0 until m) {
        p = (d * p + pattern[i].code) % q
        t = (d * t + text[i].code) % q
    }

    // Slide the pattern over text one by one
    for (i in 0..n - m) {
        // If the hash values match, check characters one by one
        if (p == t) {
            var match = true
            for (j in 0 until m) {
                if (text[i + j] != pattern[j]) {
                    match = false
                    break
                }
            }
            if (match) return i
        }

        // Calculate hash value for next window: Remove leading digit, add trailing digit
        if (i < n - m) {
            t = (d * (t - text[i].code * h) + text[i + m].code) % q
            // We might get a negative value of t, converting it to positive
            if (t < 0) t += q
        }
    }
    return -1
}

Ready? We'll be diving deeper into practice in the next stage. Be prepared to challenge your understanding, tackle problems, and see the beauty of how structured code can solve complex problems.

Above all, remember our aim is to foster a holistic understanding over mere memorization. We believe in enhancing your problem-solving skills — paving the way for success in any technical interview or real-world programming situation. Let's get started!