KMPPatternSearching.js

// Implementing KMP Search Algorithm to search all the instances of pattern in
// given text
// Reference Book: Introduction to Algorithms, CLRS

// Explanation: https://www.topcoder.com/community/competitive-programming/tutorials/introduction-to-string-searching-algorithms/

const computeLPS = (pattern) => {
 const lps = Array(pattern.length)
 lps[0] = 0
 for (let i = 1; i < pattern.length; i++) {
 let matched = lps[i - 1]
 while (matched > 0 && pattern[i] !== pattern[matched]) {
 matched = lps[matched - 1]
 }
 if (pattern[i] === pattern[matched]) {
 matched++
 }
 lps[i] = matched
 }
 return lps
}

/**
 * Returns all indices where pattern starts in text
 * @param {*} text a big text in which pattern string is to find
 * @param {*} pattern the string to find
 */
const KMPSearch = (text, pattern) => {
 if (!pattern || !text) {
 return [] // no results
 }

 // lps[i] = length of proper prefix of pattern[0]...pattern[i-1]
 // which is also proper suffix of it
 const lps = computeLPS(pattern)
 const result = []

 let matched = 0
 for (let i = 0; i < text.length; i++) {
 while (matched > 0 && text[i] !== pattern[matched]) {
 matched = lps[matched - 1]
 }
 if (text[i] === pattern[matched]) {
 matched++
 }
 if (matched === pattern.length) {
 result.push(i - pattern.length + 1)
 matched = lps[matched - 1]
 }
 }

 return result
}

export { KMPSearch }