Knuth-Morris-Prath Algorithm in Scala3 (Dotty)

I wrote at the previous post how to solve “Repeated String Match” problem from Leetcode. I tell you at the next post how to solve it linearly to string lengths. For that, I need the implementation of Knuth-Morris-Prath algorithm.

Robert Sedgewick and Kevin Wayne proposed the Java solution at their book. Gary Struthers translated it to Scala 2 code. Scala 2 code has straightforward translation to Dotty code:

class KMPplus private (pattern: String, next: Array[Int])
def search(text: String): Option[Int] =
val m = pattern.length
val n = text.length
var i = 0
var j = 0
while i < n && j < m do
while j >= 0 && text(i) != pattern(j) do
j = next(j)
j += 1
i += 1
if j == m
Some(i - m)
else
None

object KMPplus
def apply(pattern: String): KMPplus =
val next = Array.ofDim[Int](pattern.length)
var j = -1
for i <- 0 until pattern.length do
if i == 0
next(i) = -1
else if pattern(i) != pattern(j)
next(i) = j
else
next(i) = next(j)
while j >= 0 && pattern(i) != pattern(j) do
j = next(j)
j += 1
new KMPplus(pattern, next)


This code is extensively imperative. I wonder if there is a purely functional implementation of the algorithm. Twan van Laarhoven implemented it in Haskell. Also, there is the detailed explanation for the implementation at “Stack Overflow”. The implementation translated to Scala is as follows:

case class KMP[T](done: Boolean, next: T => KMP[T])

def makeTable[T](ss: List[T]): KMP[T] =
def makeTable_(xs: List[T], failure: T => KMP[T]): KMP[T] =
xs match
case List()  =>
KMP(done = true, failure)
case x :: xs =>
def success: KMP[T] =
makeTable_(xs, failure(x).next)
def test(c: T): KMP[T] =
if c == x then success else failure(c)
KMP(done = false, test)

def table: KMP[T] = makeTable_(ss, _ => table)

table

implicit class StringOps(s: String)
def isSubstrnigOf(b: String): Boolean =
@tailrec
def mtch[T](table: KMP[T], xs: List[T]): Boolean =
xs match
case List()  => table.done
case x :: xs => table.done || mtch(table.next(x), xs)

mtch(makeTable(s.toList), b.toList)


The usage:

@ "abc".isSubstrnigOf("abc")
_: Boolean = true
@ "abc".isSubstrnigOf("aabc")
_: Boolean = true
@ "abc".isSubstrnigOf("aabx")
_: Boolean = false
@ ("a" * 10).isSubstrnigOf("a" * 8 + "ba")
_: Boolean = false