KMP Pattern Matching

KMPAlgorithm.scala

package searchpattern

import scala.annotation.tailrec

/**
  * KMP Pattern Matching
  * inspired from https://www.youtube.com/watch?v=GTJr8OvyEVQ
  * Created by Arun Sethia on 6/13/18.
  */
object KMPAlgorithm extends App {

  /**
    * compute KMP index array for the pattern
    *
    * @param pattern
    * @return
    */
  def computeKmpPatternIndex(pattern: String): Array[Int] = {
    val list = pattern.toList
    val output: Array[Int] = Array.ofDim[Int](list.size)
    @tailrec
    def buildIndexArray(k: Int, left: Int): Array[Int] = {
      if (k >= list.size) output
      else {
        if (list(k) == list(left)) {
          output(k) = left + 1
          buildIndexArray(k + 1, left + 1)
        } else {
          //if not equal then find last indx where suffix is same as prefix
          output(k) = matchLastLeft(k, output(k - 1))
          buildIndexArray(k + 1, 0)
        }
      }
    }
    @tailrec
    def matchLastLeft(k: Int, left: Int): Int = {
      //if matches found then return left+1
      if (left > 0) {
        //if matches found then return left+1
        if (list(k) == list(left)) left + 1
        else matchLastLeft(k, output(left - 1)) //else previous left value will be new left
      } else 0
    }
    buildIndexArray(1, 0)
  }

  /**
    * does pattern exist for given input, pattern and pattern index array
    *
    * @param input
    * @param pattern
    * @param patternIndexArray
    * @return
    */
  def doesPatternExist(input: String, pattern: String, patternIndexArray: Array[Int]) = {
    val inputArray = input.toList
    val patternArray = pattern.toList
    @tailrec
    def checkPattern(inputIndex: Int, patternIndex: Int): Boolean = {
      if (inputIndex >= inputArray.size && patternIndex >= patternIndexArray.size)
        (patternIndex == patternIndexArray.size && inputIndex == inputArray.size)
      else {
        if (inputArray(inputIndex) == patternArray(patternIndex)) {
          //input is same as pattern so increase indexes
          checkPattern(inputIndex + 1, patternIndex + 1)
        } else {
          //input and pattern is not the same
          if (patternIndex > 1 && patternIndexArray(patternIndex - 1) > 0) {
            //if last pattern index array has value >0 means something suffix is prefix
            //so keep input index same and consider last pattern index value to compare wth
            checkPattern(inputIndex, patternIndexArray(patternIndex - 1))
          } else {
            //last pattern index array has value =0 means nothing suffix is prefix
            checkPattern(inputIndex + 1, 0)
          }
        }
      }
    }
    checkPattern(0, 0)
  }

  val patternIndexArray = computeKmpPatternIndex("abcaby")

  println(doesPatternExist("abxabcabcaby", "abcaby", patternIndexArray))
}