# KMP algorithm for pattern searching

The Knuth-Morris-Pratt (KMP) algorithm is a pattern searching algorithm that efficiently searches for occurrences of a pattern string in a text string. The KMP algorithm is based on a pre-processing step that constructs a prefix array, also known as the failure function or partial match table, which is used to avoid unnecessary comparisons during the search process.

The prefix array is computed in linear time and space complexity, and it stores the length of the longest proper prefix of the pattern string that is also a suffix of each prefix of the pattern string. This information is then used to determine the next position to compare in the text string, instead of restarting the search from the beginning of the pattern string each time there is a mismatch.

The KMP algorithm has a time complexity of O(m + n), where m is the length of the pattern string and n is the length of the text string. This makes it more efficient than naive string matching algorithms, such as the brute-force method, which has a worst-case time complexity of O(m * n).

Sure, here are the detailed steps for the KMP algorithm:

1. Pre-process the pattern string to compute the prefix array.
• Set the prefix array pi to be an array of length m (the length of the pattern string).
• Set the first element of pi, pi, to 0.
• Initialize two variables, i and j, to 0.
• While i is less than m:
• If the character at position i of the pattern string matches the character at position j of the pattern string, set pi[i] to j+1, increment both i and j.
• If the character at position i of the pattern string does not match the character at position j of the pattern string and j is not 0, set j to pi[j-1] and try again.
• If the character at position i of the pattern string does not match the character at position j of the pattern string and j is 0, set pi[i] to 0, increment i, and try again.
2. Initialize two pointers, i and j, to the beginning of the text string and the pattern string, respectively.
3. Compare the characters at positions i and j in the text and pattern strings.
4. If the characters match, increment both pointers (i and j).
5. If there is a mismatch and j is not at the beginning of the pattern string, update j to the value stored in the prefix array at position j-1, and compare again.
6. If there is a mismatch and j is at the beginning of the pattern string, increment i and repeat from step 3 until the end of the text string is reached, or a match is found.

When a match is found, the starting position of the match in the text string is i - m, where m is the length of the pattern string. If no match is found, the algorithm returns -1 or an empty result, depending on the implementation.

Here given code implementation process.

``````// C program
// KMP algorithm for pattern searching
#include <stdio.h>
#include <string.h>

// Find prefix and suffix length
void prefix_suffix(const char *pattern, int m, int position[])
{
// First position will be zero
position = 0;
int length = 0;
int i = 1;
while (i < m)
{
if (pattern[i] == pattern[length])
{
position[i] = length + 1;
length = position[i];
i++;
}
else
{
if (length != 0)
{
length = position[length - 1];
}
else
{
position[i] = 0;
i++;
}
}
}
}
// Find all location of pattern in given text
void kmp_algorithm(const char *text , const char *pattern)
{
// Get the length of pattern
int m = strlen(pattern);
// Get the length of given text
int n = strlen(text);
// Display given text and pattern
printf("\n Test    : [%s]", text);
printf("\n Pattern : [%s]", pattern);
printf("\n Pattern exist in following index : \n");
// result indicator
int status = 0;
if (m > 0 && n > 0)
{
// Loop controlling variables i and j
int i = 0;
int j = 0;
// Use to collect position of longest suffix and prefix
int position[m];
// Find position of longest prefix suffix
prefix_suffix(pattern, m, position);
// Execute loop through by text length
while (i < n)
{
if (pattern[j] == text[i])
{
j++;
i++;
}
if (j == m)
{
// When get a new pattern
printf(" Pattern at index %d\n", i - j);
j = position[j - 1];
status = 1;
}
else if (i < n && pattern[j] != text[i])
{
if (j != 0)
{
j = position[j - 1];
}
else
{
i = i + 1;
}
}
}
}
if (status == 0)
{
printf("\n None \n");
}
}
int main(int argc, char
const *argv[])
{
// Given text
const char *text = "This is historic distance division sector for tourist";
// Given pattern
const char *pattern = "is";
kmp_algorithm(text, pattern);
return 0;
}``````

#### Output

`````` Test    : [This is historic distance division sector for tourist]
Pattern : [is]
Pattern exist in following index :
Pattern at index 2
Pattern at index 5
Pattern at index 9
Pattern at index 18
Pattern at index 29
Pattern at index 50``````
``````/*
Java program
KMP algorithm for pattern searching
*/
public class Searching
{
// Find prefix and suffix length
public void prefixSuffix(String pattern, int m, int[] position)
{
// First position will be zero
position = 0;
int length = 0;
int i = 1;
while (i < m)
{
if (pattern.charAt(i) == pattern.charAt(length))
{
position[i] = length + 1;
length = position[i];
i++;
}
else
{
if (length != 0)
{
length = position[length - 1];
}
else
{
position[i] = 0;
i++;
}
}
}
}
// Find all location of pattern in given text
public void kmpAlgorithm(String text, String pattern)
{
// Get the length of pattern
int m = pattern.length();
// Get the length of given text
int n = text.length();
// Display given text and pattern
System.out.print("\n Test : [" + text + "]");
System.out.print("\n Pattern : [" + pattern + "]");
System.out.print("\n Pattern exist in following index : \n");
// result indicator
boolean status = false;
if (m > 0 && n > 0)
{
// Loop controlling variables i and j
int i = 0;
int j = 0;
// Use to collect position of longest suffix and prefix
int[] position = new int[m];
// Find position of longest prefix suffix
prefixSuffix(pattern, m, position);
// Execute loop through by text length
while (i < n)
{
if (pattern.charAt(j) == text.charAt(i))
{
j++;
i++;
}
if (j == m)
{
// When get a new pattern
System.out.print(" Pattern at index " + (i - j) + "\n");
j = position[j - 1];
status = true;
}
else if (i < n && pattern.charAt(j) != text.charAt(i))
{
if (j != 0)
{
j = position[j - 1];
}
else
{
i = i + 1;
}
}
}
}
if (status == false)
{
System.out.print("\n None \n");
}
}
public static void main(String[] args)
{
// Given text
String text = "This is historic distance division sector for tourist";
// Given pattern
String pattern = "is";
}
}``````

#### Output

`````` Test : [This is historic distance division sector for tourist]
Pattern : [is]
Pattern exist in following index :
Pattern at index 2
Pattern at index 5
Pattern at index 9
Pattern at index 18
Pattern at index 29
Pattern at index 50``````
``````// Include header file
#include <iostream>
#include <string>
using namespace std;

/*
C++ program
KMP algorithm for pattern searching
*/
class Searching
{
public:
// Find prefix and suffix length
void prefixSuffix(string pattern, int m, int position[])
{
// First position will be zero
position = 0;
int length = 0;
int i = 1;
while (i < m)
{
if (pattern[i] == pattern[length])
{
position[i] = length + 1;
length = position[i];
i++;
}
else
{
if (length != 0)
{
length = position[length - 1];
}
else
{
position[i] = 0;
i++;
}
}
}
}
// Find all location of pattern in given text
void kmpAlgorithm(string text, string pattern)
{
// Get the length of pattern
int m = pattern.length();
// Get the length of given text
int n = text.length();
// Display given text and pattern
cout << "\n Test : [" << text << "]";
cout << "\n Pattern : [" << pattern << "]";
cout << "\n Pattern exist in following index : \n";
// result indicator
bool status = false;
if (m > 0 && n > 0)
{
// Loop controlling variables i and j
int i = 0;
int j = 0;
// Use to collect position of longest suffix and prefix
int position[m];
// Find position of longest prefix suffix
this->prefixSuffix(pattern, m, position);
// Execute loop through by text length
while (i < n)
{
if (pattern[j] == text[i])
{
j++;
i++;
}
if (j == m)
{
// When get a new pattern
cout << " Pattern at index " << (i - j) << "\n";
j = position[j - 1];
status = true;
}
else if (i < n && pattern[j] != text[i])
{
if (j != 0)
{
j = position[j - 1];
}
else
{
i = i + 1;
}
}
}
}
if (status == false)
{
cout << "\n None \n";
}
}
};
int main()
{
// Given text
string text = "This is historic distance division sector for tourist";
// Given pattern
string pattern = "is";
return 0;
}``````

#### Output

`````` Test : [This is historic distance division sector for tourist]
Pattern : [is]
Pattern exist in following index :
Pattern at index 2
Pattern at index 5
Pattern at index 9
Pattern at index 18
Pattern at index 29
Pattern at index 50``````
``````// Include namespace system
using System;
/*
C# program
KMP algorithm for pattern searching
*/
public class Searching
{
// Find prefix and suffix length
public void prefixSuffix(String pattern, int m, int[] position)
{
// First position will be zero
position = 0;
int length = 0;
int i = 1;
while (i < m)
{
if (pattern[i] == pattern[length])
{
position[i] = length + 1;
length = position[i];
i++;
}
else
{
if (length != 0)
{
length = position[length - 1];
}
else
{
position[i] = 0;
i++;
}
}
}
}
// Find all location of pattern in given text
public void kmpAlgorithm(String text, String pattern)
{
// Get the length of pattern
int m = pattern.Length;
// Get the length of given text
int n = text.Length;
// Display given text and pattern
Console.Write("\n Test : [" + text + "]");
Console.Write("\n Pattern : [" + pattern + "]");
Console.Write("\n Pattern exist in following index : \n");
// result indicator
Boolean status = false;
if (m > 0 && n > 0)
{
// Loop controlling variables i and j
int i = 0;
int j = 0;
// Use to collect position of longest suffix and prefix
int[] position = new int[m];
// Find position of longest prefix suffix
prefixSuffix(pattern, m, position);
// Execute loop through by text length
while (i < n)
{
if (pattern[j] == text[i])
{
j++;
i++;
}
if (j == m)
{
// When get a new pattern
Console.Write(" Pattern at index " + (i - j) + "\n");
j = position[j - 1];
status = true;
}
else if (i < n && pattern[j] != text[i])
{
if (j != 0)
{
j = position[j - 1];
}
else
{
i = i + 1;
}
}
}
}
if (status == false)
{
Console.Write("\n None \n");
}
}
public static void Main(String[] args)
{
// Given text
String text = "This is historic distance division sector for tourist";
// Given pattern
String pattern = "is";
}
}``````

#### Output

`````` Test : [This is historic distance division sector for tourist]
Pattern : [is]
Pattern exist in following index :
Pattern at index 2
Pattern at index 5
Pattern at index 9
Pattern at index 18
Pattern at index 29
Pattern at index 50``````
``````<?php
/*
Php program
KMP algorithm for pattern searching
*/
class Searching
{
// Find prefix and suffix length
public	function prefixSuffix(\$pattern, \$m, & \$position)
{
// First position will be zero
\$position = 0;
\$length = 0;
\$i = 1;
while (\$i < \$m)
{
if (\$pattern[\$i] == \$pattern[\$length])
{
\$position[\$i] = \$length + 1;
\$length = \$position[\$i];
\$i++;
}
else
{
if (\$length != 0)
{
\$length = \$position[\$length - 1];
}
else
{
\$position[\$i] = 0;
\$i++;
}
}
}
}
// Find all location of pattern in given text
public	function kmpAlgorithm(\$text, \$pattern)
{
// Get the length of pattern
\$m = strlen(\$pattern);
// Get the length of given text
\$n = strlen(\$text);
// Display given text and pattern
echo "\n Test : [". \$text ."]";
echo "\n Pattern : [". \$pattern ."]";
echo "\n Pattern exist in following index : \n";
// result indicator
\$status = false;
if (\$m > 0 && \$n > 0)
{
// Loop controlling variables i and j
\$i = 0;
\$j = 0;
// Use to collect position of longest suffix and prefix
\$position = array_fill(0, \$m, 0);
// Find position of longest prefix suffix
\$this->prefixSuffix(\$pattern, \$m, \$position);
// Execute loop through by text length
while (\$i < \$n)
{
if (\$pattern[\$j] == \$text[\$i])
{
\$j++;
\$i++;
}
if (\$j == \$m)
{
// When get a new pattern
echo " Pattern at index ". (\$i - \$j) ."\n";
\$j = \$position[\$j - 1];
\$status = true;
}
else if (\$i < \$n && \$pattern[\$j] != \$text[\$i])
{
if (\$j != 0)
{
\$j = \$position[\$j - 1];
}
else
{
\$i = \$i + 1;
}
}
}
}
if (\$status == false)
{
echo "\n None \n";
}
}
}

function main()
{
// Given text
\$text = "This is historic distance division sector for tourist";
// Given pattern
\$pattern = "is";
}
main();``````

#### Output

`````` Test : [This is historic distance division sector for tourist]
Pattern : [is]
Pattern exist in following index :
Pattern at index 2
Pattern at index 5
Pattern at index 9
Pattern at index 18
Pattern at index 29
Pattern at index 50``````
``````/*
Node Js program
KMP algorithm for pattern searching
*/
class Searching
{
// Find prefix and suffix length
prefixSuffix(pattern, m, position)
{
// First position will be zero
position = 0;
var length = 0;
var i = 1;
while (i < m)
{
if (pattern.charAt(i) == pattern.charAt(length))
{
position[i] = length + 1;
length = position[i];
i++;
}
else
{
if (length != 0)
{
length = position[length - 1];
}
else
{
position[i] = 0;
i++;
}
}
}
}
// Find all location of pattern in given text
kmpAlgorithm(text, pattern)
{
// Get the length of pattern
var m = pattern.length;
// Get the length of given text
var n = text.length;
// Display given text and pattern
process.stdout.write("\n Test : [" + text + "]");
process.stdout.write("\n Pattern : [" + pattern + "]");
process.stdout.write("\n Pattern exist in following index : \n");
// result indicator
var status = false;
if (m > 0 && n > 0)
{
// Loop controlling variables i and j
var i = 0;
var j = 0;
// Use to collect position of longest suffix and prefix
var position = Array(m).fill(0);
// Find position of longest prefix suffix
this.prefixSuffix(pattern, m, position);
// Execute loop through by text length
while (i < n)
{
if (pattern.charAt(j) == text.charAt(i))
{
j++;
i++;
}
if (j == m)
{
// When get a new pattern
process.stdout.write(" Pattern at index " + (i - j) + "\n");
j = position[j - 1];
status = true;
}
else if (i < n && pattern.charAt(j) != text.charAt(i))
{
if (j != 0)
{
j = position[j - 1];
}
else
{
i = i + 1;
}
}
}
}
if (status == false)
{
process.stdout.write("\n None \n");
}
}
}

function main()
{
// Given text
var text = "This is historic distance division sector for tourist";
// Given pattern
var pattern = "is";
}
main();``````

#### Output

`````` Test : [This is historic distance division sector for tourist]
Pattern : [is]
Pattern exist in following index :
Pattern at index 2
Pattern at index 5
Pattern at index 9
Pattern at index 18
Pattern at index 29
Pattern at index 50``````
``````#   Python 3 program
#   KMP algorithm for pattern searching

class Searching :
#  Find prefix and suffix length
def prefixSuffix(self, pattern, m, position) :
#  First position will be zero
position = 0
length = 0
i = 1
while (i < m) :
if (pattern[i] == pattern[length]) :
position[i] = length + 1
length = position[i]
i += 1
else :
if (length != 0) :
length = position[length - 1]
else :
position[i] = 0
i += 1

#  Find all location of pattern in given text
def kmpAlgorithm(self, text, pattern) :
#  Get the length of pattern
m = len(pattern)
#  Get the length of given text
n = len(text)
#  Display given text and pattern
print("\n Test : [", text ,"]", end = "")
print("\n Pattern : [", pattern ,"]", end = "")
print("\n Pattern exist in following index : ")
#  result indicator
status = False
if (m > 0 and n > 0) :
#  Loop controlling variables i and j
i = 0
j = 0
#  Use to collect position of longest suffix and prefix
position =  * (m)
#  Find position of longest prefix suffix
self.prefixSuffix(pattern, m, position)
#  Execute loop through by text length
while (i < n) :
if (pattern[j] == text[i]) :
j += 1
i += 1

if (j == m) :
#  When get a new pattern
print(" Pattern at index ", (i - j))
j = position[j - 1]
status = True

elif(i < n and pattern[j] != text[i]) :
if (j != 0) :
j = position[j - 1]
else :
i = i + 1

if (status == False) :
print(ord("\n None \n"), end = "")

def main() :
#  Given text
text = "This is historic distance division sector for tourist"
#  Given pattern
pattern = "is"

if __name__ == "__main__": main()``````

#### Output

`````` Test : [ This is historic distance division sector for tourist ]
Pattern : [ is ]
Pattern exist in following index :
Pattern at index  2
Pattern at index  5
Pattern at index  9
Pattern at index  18
Pattern at index  29
Pattern at index  50``````
``````#   Ruby program
#   KMP algorithm for pattern searching

class Searching
#  Find prefix and suffix length
def prefixSuffix(pattern, m, position)
#  First position will be zero
position = 0
length = 0
i = 1
while (i < m)
if (pattern[i] == pattern[length])
position[i] = length + 1
length = position[i]
i += 1
else
if (length != 0)
length = position[length - 1]
else
position[i] = 0
i += 1
end

end

end

end

#  Find all location of pattern in given text
def kmpAlgorithm(text, pattern)
#  Get the length of pattern
m = pattern.length
#  Get the length of given text
n = text.length
#  Display given text and pattern
print("\n Test : [", text ,"]")
print("\n Pattern : [", pattern ,"]")
print("\n Pattern exist in following index : \n")
#  result indicator
status = false
if (m > 0 && n > 0)
#  Loop controlling variables i and j
i = 0
j = 0
#  Use to collect position of longest suffix and prefix
position = Array.new(m) {0}
#  Find position of longest prefix suffix
self.prefixSuffix(pattern, m, position)
#  Execute loop through by text length
while (i < n)
if (pattern[j] == text[i])
j += 1
i += 1
end

if (j == m)
#  When get a new pattern
print(" Pattern at index ", (i - j) ,"\n")
j = position[j - 1]
status = true
elsif(i < n && pattern[j] != text[i])
if (j != 0)
j = position[j - 1]
else
i = i + 1
end

end

end

end

if (status == false)
print("\n None \n")
end

end

end

def main()
#  Given text
text = "This is historic distance division sector for tourist"
#  Given pattern
pattern = "is"
end

main()``````

#### Output

`````` Test : [This is historic distance division sector for tourist]
Pattern : [is]
Pattern exist in following index :
Pattern at index 2
Pattern at index 5
Pattern at index 9
Pattern at index 18
Pattern at index 29
Pattern at index 50
``````
``````import scala.collection.mutable._;
/*
Scala program
KMP algorithm for pattern searching
*/
class Searching
{
// Find prefix and suffix length
def prefixSuffix(pattern: String, m: Int, position: Array[Int]): Unit = {
// First position will be zero
position(0) = 0;
var length: Int = 0;
var i: Int = 1;
while (i < m)
{
if (pattern.charAt(i) == pattern.charAt(length))
{
position(i) = length + 1;
length = position(i);
i += 1;
}
else
{
if (length != 0)
{
length = position(length - 1);
}
else
{
position(i) = 0;
i += 1;
}
}
}
}
// Find all location of pattern in given text
def kmpAlgorithm(text: String, pattern: String): Unit = {
// Get the length of pattern
var m: Int = pattern.length();
// Get the length of given text
var n: Int = text.length();
// Display given text and pattern
print("\n Test : [" + text + "]");
print("\n Pattern : [" + pattern + "]");
print("\n Pattern exist in following index : \n");
// result indicator
var status: Boolean = false;
if (m > 0 && n > 0)
{
// Loop controlling variables i and j
var i: Int = 0;
var j: Int = 0;
// Use to collect position of longest suffix and prefix
var position: Array[Int] = Array.fill[Int](m)(0);
// Find position of longest prefix suffix
this.prefixSuffix(pattern, m, position);
// Execute loop through by text length
while (i < n)
{
if (pattern.charAt(j) == text.charAt(i))
{
j += 1;
i += 1;
}
if (j == m)
{
// When get a new pattern
print(" Pattern at index " + (i - j) + "\n");
j = position(j - 1);
status = true;
}
else if (i < n && pattern.charAt(j) != text.charAt(i))
{
if (j != 0)
{
j = position(j - 1);
}
else
{
i = i + 1;
}
}
}
}
if (status == false)
{
print("\n None \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Searching = new Searching();
// Given text
var text: String = "This is historic distance division sector for tourist";
// Given pattern
var pattern: String = "is";
}
}``````

#### Output

`````` Test : [This is historic distance division sector for tourist]
Pattern : [is]
Pattern exist in following index :
Pattern at index 2
Pattern at index 5
Pattern at index 9
Pattern at index 18
Pattern at index 29
Pattern at index 50``````
``````/*
Swift 4 program
KMP algorithm for pattern searching
*/
class Searching
{
// Find prefix and suffix length
func prefixSuffix(_ pattern: [Character], _ m: Int, _ position: inout[Int])
{
// First position will be zero
position = 0;
var length: Int = 0;
var i: Int = 1;
while (i < m)
{
if (pattern[i] == pattern[length])
{
position[i] = length + 1;
length = position[i];
i += 1;
}
else
{
if (length  != 0)
{
length = position[length - 1];
}
else
{
position[i] = 0;
i += 1;
}
}
}
}
// Find all location of pattern in given text
func kmpAlgorithm(_ t: String, _ p: String)
{
// Convert into character array
let pattern = Array(p);
let text    = Array(t);
// Get the length of pattern
let m: Int = pattern.count;
// Get the length of given text
let n: Int = text.count;
// Display given text and pattern
print("\n Test : [", t ,"]", terminator: "");
print("\n Pattern : [", p ,"]", terminator: "");
print("\n Pattern exist in following index : ");
// result indicator
var status: Bool = false;
if (m > 0 && n > 0)
{
// Loop controlling variables i and j
var i: Int = 0;
var j: Int = 0;
// Use to collect position of longest suffix and prefix
var position: [Int] = Array(repeating: 0, count: m);
// Find position of longest prefix suffix
self.prefixSuffix(pattern, m, &position);
// Execute loop through by text length
while (i < n)
{
if (pattern[j] == text[i])
{
j += 1;
i += 1;
}
if (j == m)
{
// When get a new pattern
print(" Pattern at index ", (i - j) );
j = position[j - 1];
status = true;
}
else if (i < n && pattern[j]  != text[i])
{
if (j  != 0)
{
j = position[j - 1];
}
else
{
i = i + 1;
}
}
}
}
if (status == false)
{
print("\n None ");
}
}
}
func main()
{
// Given text
let text: String = "This is historic distance division sector for tourist";
// Given pattern
let pattern: String = "is";
}
main();``````

#### Output

`````` Test : [ This is historic distance division sector for tourist ]
Pattern : [ is ]
Pattern exist in following index :
Pattern at index  2
Pattern at index  5
Pattern at index  9
Pattern at index  18
Pattern at index  29
Pattern at index  50``````
``````/*
Kotlin program
KMP algorithm for pattern searching
*/
class Searching
{
// Find prefix and suffix length
fun prefixSuffix(pattern: String, m: Int, position: Array < Int > ): Unit
{
// First position will be zero
position = 0;
var length: Int = 0;
var i: Int = 1;
while (i < m)
{
if (pattern.get(i) == pattern.get(length))
{
position[i] = length + 1;
length = position[i];
i += 1;
}
else
{
if (length != 0)
{
length = position[length - 1];
}
else
{
position[i] = 0;
i += 1;
}
}
}
}
// Find all location of pattern in given text
fun kmpAlgorithm(text: String, pattern: String): Unit
{
// Get the length of pattern
var m: Int = pattern.length;
// Get the length of given text
var n: Int = text.length;
// Display given text and pattern
print("\n Test : [" + text + "]");
print("\n Pattern : [" + pattern + "]");
print("\n Pattern exist in following index : \n");
// result indicator
var status: Boolean = false;
if (m > 0 && n > 0)
{
// Loop controlling variables i and j
var i: Int = 0;
var j: Int = 0;
// Use to collect position of longest suffix and prefix
var position: Array < Int > = Array(m)
{
0
};
// Find position of longest prefix suffix
this.prefixSuffix(pattern, m, position);
// Execute loop through by text length
while (i < n)
{
if (pattern.get(j) == text.get(i))
{
j += 1;
i += 1;
}
if (j == m)
{
// When get a new pattern
print(" Pattern at index " + (i - j) + "\n");
j = position[j - 1];
status = true;
}
else if (i < n && pattern.get(j) != text.get(i))
{
if (j != 0)
{
j = position[j - 1];
}
else
{
i = i + 1;
}
}
}
}
if (status == false)
{
print("\n None \n");
}
}
}
fun main(args: Array < String > ): Unit
{
// Given text
var text: String = "This is historic distance division sector for tourist";
// Given pattern
var pattern: String = "is";
}``````

#### Output

`````` Test : [This is historic distance division sector for tourist]
Pattern : [is]
Pattern exist in following index :
Pattern at index 2
Pattern at index 5
Pattern at index 9
Pattern at index 18
Pattern at index 29
Pattern at index 50``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.