Code Review Asked by gil.fernandes on October 27, 2021
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
.
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP