Substring Searching – HackerRank Solution

In this post, we will solve Substring Searching HackerRank Solution. This problem (Substring Searching) is a part of HackerRank Functional Programming series.

Task

In 1974, a very fast string searching method was proposed by the name of KMP algorithm with linear run-time complexity. Your task here is to code this (or any similar) algorithm in a functional language.

Given two strings text and pat, find whether pat exists as a substring in text.

Input

First line will contain an integer, T, which represents total number of test cases. Then T test cases follow. Each case will contains two lines each containing a string. First line will contain text while the second line will contain pat.

Output

For each case print YES if pat is a substring of text otherwise NO.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ |pat| ≤ |text| ≤ 100000
• All characters in text and pat will be lowercase latin character (‘a‘-‘z‘).

Sample Input

4
abcdef
def
computer
muter
stringmatchingmat
ingmat
videobox
videobox

Sample Output

YES
NO
YES
YES

Explanation

Test Case #00: Here “def” is present at the end of “abcdef”.
Test Case #01: Though “muter” is a subsequence here, but we need it to be asubstring.
Test Case #02: _”ingmat”_ is present at index 3 and 11.
Test Case #03: Both strings are same.

Solution – Substring Searching – HackerRank Solution

Scala

import java.util.Scanner

object Solution {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)

    val t = sc.nextInt
    sc.nextLine

    (0 until t).foreach(_ => {
      val s = sc.nextLine
      val w = sc.nextLine

      println(if (search(w, s).isEmpty) "NO" else "YES")
    })

    sc.close()
  }

  def search(pat: String, txt: String): List[Int] = {
    val lps = buildLps(pat)

    @scala.annotation.tailrec
    def inner(i: Int, j: Int, acc: List[Int]): List[Int] = if (i < txt.length) {
      val (nextI, nextJ) = if (pat(j) == txt(i)) {
        (i + 1, j + 1)
      } else {
        if (j == 0) (i + 1, 0) else (i, lps(j - 1))
      }

      val found = nextJ == pat.length
      inner(nextI, if (found) lps(nextJ - 1) else nextJ, if (found) nextI - nextJ :: acc else acc)
    } else acc

    inner(0, 0, Nil)
  }

  def buildLps(w: String): IndexedSeq[Int] = {
    val n = w.length
    val lps = Array.ofDim[Int](n)

    lps(0) = 0

    @scala.annotation.tailrec
    def inner(i: Int, len: Int): Unit = if (i < n) {
      val (nextI, nextLen) = if (w(i) == w(len)) {
        (i + 1, len + 1)
      } else {
        if (len == 0) (i + 1, 0) else (i, lps(len - 1))
      }

      lps(i) = nextLen
      inner(nextI, nextLen)
    }

    inner(1, 0)

    lps.toIndexedSeq
  }
}

Note: This problem (Substring Searching) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.