# 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.

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.