1
\$\begingroup\$

I implemented KMP pattern matching algorithm in Scala. My code works but it looks more imperative and a scala translation of C/C++ implementation.

I am not able to figure out how to manage multiple indexes and then update them conditionally. Following is the code with some explanation, kindly suggest how to write it in scala way.

KMP algo has two parts .

first one is where we create an array which will have information of how many character we can skip in pattern if find a mismatch.

example -

AAAA -> 0,1,2,3
ABCDE  -> 0,0,0,0,0
AABAACAABAA -> 0,1,0,1,2,0,1,2,3,4,5

Following is code to build this array from patten string

def buildLookupTable(s: String): ArrayBuffer[Int] = {
    val lookupTable = ArrayBuffer.fill(s.length)(-1)
    lookupTable(0) = 0 // first char always 0
    var len = 0
    var i = 1
    while( i < s.length) {
      if (s(i) == s(len)) {
        len += 1
        lookupTable(i) = len
        i += 1
      } else { // mismatch
        if (len == 0) {
          lookupTable(i) = 0;
          i= i+1
        } else {
          len = lookupTable(len-1)
        }
      }
    }
    lookupTable
  }

Once we have this array we can use this to find occurences of a pattern. Something like following

def searchPattern(s: String, p: String): Unit = {
    if (p.length > s.length) println("bad input")
    else if (p == s) println("same strings")
    else {
      val lookupTable = buildLookupTable(p)

      var i= 0 // for s
      var j= 0 // for p

      while (i < s.length) {
        if (s(i) == p(j)) {
          i += 1
          j += 1
        }
        if (j == p.length) {
          println(s"pattern found at ${i-j}")
          j = lookupTable(j-1)
        }
        else {
          if (i < s.length && s(i) != p(j)) {
            if (j != 0) j = lookupTable(j-1)
            else i+=1
          }
        }
      }
    }
  }

This code works for the tests cases I have. But its not beautiful scala code. Kindly suggest the right approach to look at this problem and solve it functional way.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.