ZAlgorithm for String pattern search

ZAlgorithm.scala

package searchpattern

import scala.annotation.tailrec


/**
  * ZIndex String Pattern Search
  * inspired from https://www.youtube.com/watch?v=CpZh4eF8QBw
  * Created by Arun Sethia on 6/6/18.
  */
abstract class ZAlgorithm(val input: String, val pattern: String) {
  val zString: List[Char] = buildZIndexString
  val zLen = zString.length
  val zIndex = Array.ofDim[Int](zLen)

  def buildZIndexString: List[Char]

  /**
    * compute Z Index
    *
    * @param right
    * @param left
    * @param k
    */
  def computeZIndex(right: Int, left: Int, k: Int): Unit = {
    if (k < zLen) {
      if (k > right) {
        //keep right , left same as k
        computeZIndex(computeZNormal(k, k, k), k, k + 1)
      } else {
        //operating inside box
        val k1 = k - left
        //if value does not stretches till right bound then just copy it.
        if (k1 < zIndex(left)) {
          zIndex(k) = zIndex(k1)
        }
        computeZIndex(right, left, k + 1)
      }
    }
  }

  /**
    * compute Z Normal
    *
    * @param right
    * @param left
    * @param k
    * @return
    */
  @tailrec
  final def computeZNormal(right: Int, left: Int, k: Int): Int = {
    if (right < zLen && zString(right) == zString(right - left)) {
      computeZNormal(right + 1, left, k)
    } else {
      zIndex(k) = right - left
      right - 1
    }
  }

  /**
    * get zIndex
    *
    * @return
    */
  def getZIndex() = zIndex

  /**
    * find matched index
    *
    * @return
    */
  def findMatchedIndex(): List[Int] = {
    val zIndexWithIndex = zIndex.zipWithIndex
    val subPattLen = pattern.length + 1 //1 for special char
    zIndexWithIndex
      .filter(a => a._1 == pattern.length)
      .map(res => res._2 - subPattLen).toList
  }
}


object ZAlgorithm extends App {
  val s = "aabxaayaab"
  val zIndexAlgo = new ZAlgorithm(s, "abc") {
    def buildZIndexString: List[Char] = (input).toList
  }
  zIndexAlgo.computeZIndex(0, 0, 1)
  println("ZIndex:"+zIndexAlgo.zIndex.map(_.toString).mkString(","))
  val result = zIndexAlgo.findMatchedIndex().mkString(",")
  println(s"matched index ${result}")
}