# Knuth–Morris–Pratt Algorithm for Pattern Matching Implementation in Javascript

Category : TECH Author : Ayush Kush Date : Mon Jul 25 2016 Views : 127

### Algorithm

Knuth–Morris–Pratt Algorithm also known as KMP Algorithm is a well known algorithm for pattern matching.

As per wikipedia, In computer science, KMP searches for occurrences of a "word" `W`

within a main "text string" `S`

by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

### Problem

Let us look at some examples to understand the problem in a better way

Lets say we have one string as

S1 = AABBCCDDEEFFAABBCC

S2 = AABB

If we search for pattern S2 in S1 to find its occurrence
than we will say that S2 is present at 0 and 12 position.

Let see another example

Lets say we have one string as

S1 = ABCABYCBYABCABY

S2 = ABCABY

If we search for pattern S2 in S1 to find its occurrence
than we will say that S2 is present at 0 and 9 position.

So one way is to search each character of S2 in S1. But that will be inefficient as time complexity for that will be O(m*n) where m is the length of S2 and n is the length of S2.

Thats why we use KMP algorithm in which first we create **LPS Array of S2** which stands for longest proper prefix which is also suffix and then we find pattern using LPS[] and S1.

### Algorithm

Let us understand algorithm first

Algo to create LSP array is

**/*** Algo for creating LPS Array ***/**

// Push 0 to the first element of LPS Array as it is always 0

// Initalise j to the 1st character and i to the second character

// check if the element at i is equal to jth element

// if yes than increment j and make LPSArray[i] = j and then increment i

// if no than check if LPS[j] is 0 or not

// if yes than LPS[i] = 0 and j++, i++;

// if no than we will find the value at LPS[j-1]
// and then j will pat[LPS[j-1]] and then we will start
// matching i and j again as per steps written above.

Now let us see Algo for KMP Pattern Search

**/** Algo for KMP Patttern Search **/**

// Initalise i = 0 , j = 0;

// Create LPS Array by calling LPS array method.

// compare str[i] with pat[j]

// check if str[i] === pat[j]

// if yes than check whether j === pat.length

// if yes than print that pattern found at (i-j), i++,j=0

// if no i++,j++

// if not than check if j === 0

// if yes than i++;

// if no then j = LPSArray[j-1]

### Code

let us bind code and algo to form full KMP Search Code with algorithms

"use strict";

**/** Algo for KMP Patttern Search **/**

// Initalise i = 0 , j = 0;

// Create LPS Array by calling LPS array method.

// compare str[i] with pat[j]

// check if str[i] === pat[j]

// if yes than check whether j === pat.length

// if yes than print that pattern found at (i-j), i++,j=0

// if no i++,j++

// if not than check if j === 0

// if yes than i++;

// if no then j = LPSArray[j-1]

function KMPPatterSearch(str, pat){

var i,j;

var LPSArray;

i = 0;

j = 0;

if(!pat.length || !str.length){

return;

}

LPSArray = createLPSArray(pat);

while(i < str.length){

if(str[i] === pat[j]){

if(j === (pat.length - 1)){

console.log("Pattern found at " + (i-j))

i++;

j = 0;

} else {

i++;

j++;

}

} else {

if(j === 0){

i++;

} else {

j = LPSArray[j-1];

}

}

}

}

**/*** Algo for creating LPS Array ***/**

// Push 0 to the first element of LPS Array as it is always 0

// Initalise j to the 1st character and i to the second character

// check if the element at i is equal to jth element

// if yes than increment j and make LPSArray[i] = j and then increment i

// if no than check if LPS[j] is 0 or not

// if yes than LPS[i] = 0 and j++, i++;

// if no than we will find the value at LPS[j-1] and then j will pat[LPS[j-1]] and then we will start matching i and j again as per steps written above.

function createLPSArray(pat){

var LPSArray = [];

var i,j;

LPSArray[0] = 0;

i = 1;

j = 0;

while(i < pat.length){

if(pat[i] === pat[j]){

j++;

LPSArray[i] = j;

i++;

} else {

if(LPSArray[j] !== 0){

j = LPSArray[j-1];

} else {

LPSArray[i] = 0;

i++;

}

}

}

return LPSArray;

}

### Test cases

(function(){

var str = process.argv[3] || "ABCABCABCABCABC";

var pat = process.argv[2] || "ABC";

KMPPatterSearch(str, pat);

}());

### Run Code

Now let us run the above code

> **node KMPPatternMatching_Algo.js**

Pattern found at 0

Pattern found at 3

Pattern found at 6

Pattern found at 9

Pattern found at 12

You can find the full code here https://github.com/oyewiki/DataStructures/blob/master/Algo/KMPPatternMatching_Algo.js

### Algorithm

Knuth–Morris–Pratt Algorithm also known as KMP Algorithm is a well known algorithm for pattern matching.

As per wikipedia, In computer science, KMP searches for occurrences of a "word" `W`

within a main "text string" `S`

by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

### Problem

Let us look at some examples to understand the problem in a better way

Lets say we have one string as

S1 = AABBCCDDEEFFAABBCC

S2 = AABB

If we search for pattern S2 in S1 to find its occurrence
than we will say that S2 is present at 0 and 12 position.

Let see another example

Lets say we have one string as

S1 = ABCABYCBYABCABY

S2 = ABCABY

If we search for pattern S2 in S1 to find its occurrence
than we will say that S2 is present at 0 and 9 position.

So one way is to search each character of S2 in S1. But that will be inefficient as time complexity for that will be O(m*n) where m is the length of S2 and n is the length of S2.

Thats why we use KMP algorithm in which first we create **LPS Array of S2** which stands for longest proper prefix which is also suffix and then we find pattern using LPS[] and S1.

### Algorithm

Let us understand algorithm first

Algo to create LSP array is

**/*** Algo for creating LPS Array ***/**

// Push 0 to the first element of LPS Array as it is always 0

// Initalise j to the 1st character and i to the second character

// check if the element at i is equal to jth element

// if yes than increment j and make LPSArray[i] = j and then increment i

// if no than check if LPS[j] is 0 or not

// if yes than LPS[i] = 0 and j++, i++;

// if no than we will find the value at LPS[j-1]
// and then j will pat[LPS[j-1]] and then we will start
// matching i and j again as per steps written above.

Now let us see Algo for KMP Pattern Search

**/** Algo for KMP Patttern Search **/**

// Initalise i = 0 , j = 0;

// Create LPS Array by calling LPS array method.

// compare str[i] with pat[j]

// check if str[i] === pat[j]

// if yes than check whether j === pat.length

// if yes than print that pattern found at (i-j), i++,j=0

// if no i++,j++

// if not than check if j === 0

// if yes than i++;

// if no then j = LPSArray[j-1]

### Code

let us bind code and algo to form full KMP Search Code with algorithms

"use strict";

**/** Algo for KMP Patttern Search **/**

// Initalise i = 0 , j = 0;

// Create LPS Array by calling LPS array method.

// compare str[i] with pat[j]

// check if str[i] === pat[j]

// if yes than check whether j === pat.length

// if yes than print that pattern found at (i-j), i++,j=0

// if no i++,j++

// if not than check if j === 0

// if yes than i++;

// if no then j = LPSArray[j-1]

function KMPPatterSearch(str, pat){

var i,j;

var LPSArray;

i = 0;

j = 0;

if(!pat.length || !str.length){

return;

}

LPSArray = createLPSArray(pat);

while(i < str.length){

if(str[i] === pat[j]){

if(j === (pat.length - 1)){

console.log("Pattern found at " + (i-j))

i++;

j = 0;

} else {

i++;

j++;

}

} else {

if(j === 0){

i++;

} else {

j = LPSArray[j-1];

}

}

}

}

**/*** Algo for creating LPS Array ***/**

// Push 0 to the first element of LPS Array as it is always 0

// Initalise j to the 1st character and i to the second character

// check if the element at i is equal to jth element

// if yes than increment j and make LPSArray[i] = j and then increment i

// if no than check if LPS[j] is 0 or not

// if yes than LPS[i] = 0 and j++, i++;

// if no than we will find the value at LPS[j-1] and then j will pat[LPS[j-1]] and then we will start matching i and j again as per steps written above.

function createLPSArray(pat){

var LPSArray = [];

var i,j;

LPSArray[0] = 0;

i = 1;

j = 0;

while(i < pat.length){

if(pat[i] === pat[j]){

j++;

LPSArray[i] = j;

i++;

} else {

if(LPSArray[j] !== 0){

j = LPSArray[j-1];

} else {

LPSArray[i] = 0;

i++;

}

}

}

return LPSArray;

}

### Test cases

(function(){

var str = process.argv[3] || "ABCABCABCABCABC";

var pat = process.argv[2] || "ABC";

KMPPatterSearch(str, pat);

}());

### Run Code

Now let us run the above code

> **node KMPPatternMatching_Algo.js**

Pattern found at 0

Pattern found at 3

Pattern found at 6

Pattern found at 9

Pattern found at 12

You can find the full code here https://github.com/oyewiki/DataStructures/blob/master/Algo/KMPPatternMatching_Algo.js

**Disclaimer:** The above content reflect author’s personal views and do not reflect the views of OYEWIKI. Neither OYEWIKI nor any person/organization acting on its behalf is liable to accept any legal liability/responsibility for any error/mislead in this information or any information available on the website. This website in no way accepts the responsibility for any loss, injury, damage, discomfort or inconvenience caused as a result of reliance on any information provided on this website.

If you want to add more comments to the article or you see any thing incorrect please write a comment below and we will surely get back to you.