KMP (Knuth Morris Pratt) pattern search implementation

KMPPatternSearch.scala

import scala.annotation.tailrec

/**
 * KMP (Knuth Morris Pratt) pattern search implementation
 */

import KMPPatternSearch._

assert(auxPattern("abcdabca".toCharArray) == List(0, 0, 0, 0, 1, 2, 3, 1))
assert(auxPattern("aabaabaaa".toCharArray) == List(0, 1, 0, 1, 2, 3, 4, 5, 2))
assert(auxPattern("abcaby".toCharArray) == List(0, 0, 0, 1, 2, 0))

assert(search("AAAAB", "AAAAAAAAAAAAAAAAAB") == List(13))
assert(search("ABABAC", "ABABABCABABABCABABABC") == Nil)
assert(search("TEST", "THIS IS A TEST TEXT") == List(10))
assert(search("AABA", "AABAACAADAABAABA").reverse == List(0, 9, 12))


def auxPattern(pattern: Array[Char]): List[Int] = {
  @tailrec
  def _matching(i: Int, j: Int, acc: List[Int]): List[Int] =
    if (i == acc.size) acc
    else {
      if (pattern(i) == pattern(j)) {
        _matching(i + 1, j + 1, acc.updated(i, j + 1))
      } else {
        if (j == 0)
          _matching(i + 1, 0, acc)
        else
          _matching(i, acc(j - 1), acc)
      }
    }

  _matching(1, 0, List.fill(pattern.length)(0))
}

def search(pattern: String, text: String): List[Int] = {
  val patternLen = pattern.length - 1
  val patternTable = auxPattern(pattern.toCharArray)

  @tailrec
  def _search(startPos: Int, i: Int, patternNdx: Int, acc: List[Int]): List[Int] =
    if (startPos == text.length || startPos + i == text.length) acc
    else if (text(startPos + i) == pattern(i)) {
      if (i == patternLen)
        _search(startPos + i, 0, 0, startPos :: acc)
      else _search(startPos, i + 1, patternNdx, acc)
    } else {
      if (patternNdx == 0)
        _search(startPos + 1, 0, 0, acc)
      else
        _search(startPos + 1, 0, patternTable(patternNdx - 1), acc)
    }

  _search(0, 0, 0, Nil)
}