trjhtr

Below you can find a Kotlin based implementation of the Knuth Morris Pratt substring search algorithm. Here is the corresponding Wikipedia article.

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.