Knuth Morris Pratt substring search algorithm

Question

Below you can find a Kotlin based implementation of the Knuth-Morris-Pratt substring search algorithm.

class KnutMorrisPrat(R: Int, private val pat: String) {

    private val m = pat.length

    private val dfa: Array<Array<Int>> = Array(R) { Array(m) { 0 } }

    constructor(pat: CharArray) : this(256, String(pat))

    constructor(pat: String) : this(256, pat)

    init {
        dfa[pat[0].toInt()][0] = 1
        var x = 0
        var j = 1
        while(j < m) {
            (0 until R).forEach { c -> dfa[c][j] = dfa[c][x] } // Copy mismatch cases.
            dfa[pat[j].toInt()][j] = j + 1                     // Set match case.
            x = dfa[pat[j].toInt()][x]                         // Update restart state.
            j++                                                // Move to next character in pattern
        }
    }

    fun search(txt: String): Int {
        return doSearch(txt, 0)
    }

    fun search(txt: String, start: Int): Int {
        return doSearch(txt, start)
    }

    private fun doSearch(txt: String, start: Int): Int {
        val m = pat.length
        val n = txt.length
        var i = start
        var j = 0
        while(i < n && j < m) {
            j = dfa[txt[i++].toInt()][j]
        }
        return if (j == m) i - m else -1
    }
}

Here is a unit test, using JUnit 4:

import org.hamcrest.core.Is
import org.junit.Assert.assertThat
import org.junit.Test

class KnutMorrisPratTest {

    @Test
    fun search() {
        val text = "All we're supposed to know about is our patter pattern. And we're supposed to light the light if we find our pattern and that's it"
        assertThat(KnutMorrisPrat("we").search(text), Is.`is`(text.indexOf("we")))
        assertThat(KnutMorrisPrat("All").search(text), Is.`is`(text.indexOf("All")))
        assertThat(KnutMorrisPrat("know").search(text), Is.`is`(text.indexOf("know")))
        assertThat(KnutMorrisPrat("pattern").search(text), Is.`is`(text.indexOf("pattern")))
        assertThat(KnutMorrisPrat("supposed").search(text), Is.`is`(text.indexOf("supposed")))
        assertThat(KnutMorrisPrat("patter").search(text), Is.`is`(text.indexOf("patter")))
        assertThat(KnutMorrisPrat("that's").search(text), Is.`is`(text.indexOf("that's")))
        assertThat(KnutMorrisPrat("pattern").search(text, 57), Is.`is`(text.indexOf("pattern", 57)))
        assertThat(KnutMorrisPrat(127,"pattern").search(text, 57), Is.`is`(text.indexOf("pattern", 57)))
        assertThat(KnutMorrisPrat("pattern".toCharArray()).search(text, 57), Is.`is`(text.indexOf("pattern", 57)))
        assertThat(KnutMorrisPrat("asddada".toCharArray()).search(text), Is.`is`(text.indexOf("asddada")))
    }

}

The search should give the same results as java.lang.String.indexOf.