Rabin-Karp algorithm in Kotlin

The Rabin-Karp algorithm is a string searching algorithm that finds the occurrence of a pattern string P in a text string T with a time complexity of O(n+m), where n is the length of T and m is the length of P. The algorithm uses hashing to efficiently compare the pattern with substrings of the text.

The algorithm works by first computing the hash value of the pattern string P, and then sliding a window of length m over the text string T, computing the hash value of each substring of length m. If the hash value of the substring matches the hash value of the pattern, then the algorithm compares each character in the substring with the corresponding character in the pattern to confirm the match.

To compute the hash value of a substring, the algorithm uses a rolling hash function that updates the hash value based on the previous hash value and the new character being added or removed from the window. This allows the algorithm to avoid recomputing the hash value of the entire substring for each window shift, resulting in a faster runtime.

Overall, the Rabin-Karp algorithm is a simple and efficient algorithm for string searching that is particularly useful when searching for multiple patterns in a single text string.

Kotlin


fun rabinKarp(text: String, pattern: String): Int {
    val n = text.length
    val m = pattern.length
    val prime = 101 // a prime number used in the hash function
    val pow = pow1(prime,(m - 1)) // precompute the value of prime^(m-1)

    // compute the hash value of the pattern and the first window of the text
    var patternHash = 0
    var windowHash = 0
    for (i in 0 until m) {
        patternHash = (prime * patternHash + pattern[i].toInt()) % Int.MAX_VALUE
        windowHash = (prime * windowHash + text[i].toInt()) % Int.MAX_VALUE
    }

    // slide the window over the text and compare the hash values
    for (i in 0..n-m) {
        if (windowHash == patternHash && text.substring(i, i+m) == pattern) {
            return i // match found
        }
        if (i < n-m) {
            // update the hash value of the window
            windowHash = (prime * (windowHash - text[i].toInt() * pow) +
                          text[i+m].toInt()) % Int.MAX_VALUE
            if (windowHash < 0) {
                windowHash += Int.MAX_VALUE
            }
        }
    }

    return -1 // no match found
}
fun pow1(base: Int, exponent: Int): Int {
    var result = 1
    for (i in 0 until exponent) {
        result *= base
    }
    return result
}

fun main() {
    val text = "Lorem ipsum dolor sit amet, consectetur adipiscing elit."
    val pattern = "ipsum"
    val index = rabinKarp(text, pattern)
    if (index != -1) {
        println("Pattern found at index $index")
    } else {
        println("Pattern not found")
    }
}
Open in Playground →
Target: JVM
Running on v.1.8.10

In this example, the rabinKarp function takes in two strings, text and pattern, and returns the starting index of the first occurrence of pattern in text, or -1 if pattern is not found in text. The function uses a prime number 101 as the base of the hash function, and precomputes the value of prime^(m-1) to avoid recomputing it for each window shift. The function then slides a window of length m over the text string, computing the hash value of each substring of length m and comparing it with the hash value of the pattern string. If a match is found, the function returns the starting index of the match. Otherwise, the function returns -1 if no match is found.

the main function defines a text string and a pattern string. It then calls the rabinKarp function with text and pattern as arguments to search for the pattern in the text. If the rabinKarp function returns an index other than -1, indicating that the pattern was found, the main function prints a message indicating the index where the pattern was found. Otherwise, it prints a message indicating that the pattern was not found.

Leave a Comment Cancel reply