
Linear-Time Substring Search with Knuth-Morris-Pratt in JavaScript
A naive nested-loop substring search compares characters from left to right and, upon hitting a mismatch, rewinds the text cursor all the way back to one position past where the previous attempt began. On repetitive inputs—such as DNA sequences, structured log streams, or source code filled with repeated tokens—this constant rewinding degrades worst-case time complexity to $O(N \cdot M)$, where $N$ is the text length and $M$ is the pattern length, re-inspecting characters that were already proven to match.
The Knuth-Morris-Pratt (KMP) algorithm guarantees strict $O(N + M)$ worst-case execution time with $O(M)$ auxiliary space by never moving the main text pointer backward. Before scanning the input, KMP preprocesses the pattern into a Longest Proper Prefix which is also a Suffix (LPS) table; whenever a mismatch occurs at index j of the pattern, lps[j - 1] tells the matcher exactly how many already-matched characters can be reused immediately, skipping redundant comparisons in both batch searches and streaming text scanners.
Example
function buildLpsTable(pattern) {
const lps = new Array(pattern.length).fill(0);
let prefixLen = 0;
for (let i = 1; i < pattern.length; i += 1) {
while (prefixLen > 0 && pattern[i] !== pattern[prefixLen]) {
prefixLen = lps[prefixLen - 1];
}
if (pattern[i] === pattern[prefixLen]) {
prefixLen += 1;
lps[i] = prefixLen;
}
}
return lps;
}
console.log(buildLpsTable('ababcabab')); // [0, 0, 1, 2, 0, 1, 2, 3, 4]
Implementation
/**
* Builds the Longest Proper Prefix-Suffix (LPS) failure table for a pattern.
* Time complexity: O(M), Space complexity: O(M).
*
* @param {string} pattern
* @returns {Int32Array}
*/
export function buildLpsTable(pattern) {
const m = pattern.length;
const lps = new Int32Array(m);
let len = 0;
let i = 1;
while (i < m) {
if (pattern.charCodeAt(i) === pattern.charCodeAt(len)) {
len += 1;
lps[i] = len;
i += 1;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i += 1;
}
}
return lps;
}
/**
* Finds all starting indices of `pattern` inside `text` in O(N + M) time.
* Supports overlapping matches cleanly without backtracking `text`.
*
* @param {string} text
* @param {string} pattern
* @returns {number[]}
*/
export function kmpSearchAll(text, pattern) {
if (pattern.length === 0 || text.length < pattern.length) {
return [];
}
const lps = buildLpsTable(pattern);
const matches = [];
let textIndex = 0;
let patternIndex = 0;
while (textIndex < text.length) {
if (text.charCodeAt(textIndex) === pattern.charCodeAt(patternIndex)) {
textIndex += 1;
patternIndex += 1;
if (patternIndex === pattern.length) {
matches.push(textIndex - patternIndex);
// Fall back via LPS to continue scanning for overlapping matches
patternIndex = lps[patternIndex - 1];
}
} else if (patternIndex > 0) {
patternIndex = lps[patternIndex - 1];
} else {
textIndex += 1;
}
}
return matches;
}
/**
* Stateful streaming KMP matcher for chunked log or network text processing.
*/
export class StreamingKmpMatcher {
#pattern;
#lps;
#patternIndex = 0;
#offset = 0;
/**
* @param {string} pattern
*/
constructor(pattern) {
if (!pattern) {
throw new RangeError('Pattern must be a non-empty string');
}
this.#pattern = pattern;
this.#lps = buildLpsTable(pattern);
}
/**
* Processes the next text chunk and returns global match start offsets.
*
* @param {string} chunk
* @returns {number[]}
*/
push(chunk) {
const foundOffsets = [];
for (let i = 0; i < chunk.length; i += 1) {
const charCode = chunk.charCodeAt(i);
while (
this.#patternIndex > 0 &&
charCode !== this.#pattern.charCodeAt(this.#patternIndex)
) {
this.#patternIndex = this.#lps[this.#patternIndex - 1];
}
if (charCode === this.#pattern.charCodeAt(this.#patternIndex)) {
this.#patternIndex += 1;
if (this.#patternIndex === this.#pattern.length) {
foundOffsets.push(this.#offset + i - this.#pattern.length + 1);
this.#patternIndex = this.#lps[this.#patternIndex - 1];
}
}
}
this.#offset += chunk.length;
return foundOffsets;
}
}
// Example verification on repetitive input and chunked stream
const occurrences = kmpSearchAll('aaabaabaaabaaaba', 'aaab');
console.log('Batch match indices:', occurrences); // [0, 7, 11]
const matcher = new StreamingKmpMatcher('ERROR_TIMEOUT');
console.log(matcher.push('2025-09-24 INFO ok; ERROR_')); // []
console.log(matcher.push('TIMEOUT on node-2')); // [20]
Main Point: The Knuth-Morris-Pratt algorithm eliminates worst-case string search backtracking by reusing matched prefix information stored in an LPS table for guaranteed linear-time scanning.
Credits
Photo by Milad Fakurian on Unsplash