GeezerVison

// 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 }