KMP Search

Find a pattern in text in linear time, using a table of the longest prefix that is also a suffix.

JAVASCRIPT Free to use

Code

class KmpMatcher {
    constructor(pattern) {
        if (typeof pattern !== 'string') {
            throw new TypeError('pattern must be a string.');
        }

        this.pattern = pattern;
        this.table = this.buildTable(pattern);
    }

    search(text) {
        if (typeof text !== 'string' || this.pattern.length === 0) {
            return [];
        }

        const found = [];
        let taken = 0;

        for (let index = 0; index < text.length; index += 1) {
            while (taken > 0 && text[index] !== this.pattern[taken]) {
                taken = this.table[taken - 1];
            }

            if (text[index] === this.pattern[taken]) {
                taken += 1;
            }

            if (taken === this.pattern.length) {
                found.push(index - taken + 1);
                taken = this.table[taken - 1];
            }
        }

        return found;
    }

    indexOf(text) {
        if (typeof text !== 'string' || this.pattern.length === 0) {
            return -1;
        }

        let taken = 0;

        for (let index = 0; index < text.length; index += 1) {
            while (taken > 0 && text[index] !== this.pattern[taken]) {
                taken = this.table[taken - 1];
            }

            if (text[index] === this.pattern[taken]) {
                taken += 1;
            }

            if (taken === this.pattern.length) {
                return index - taken + 1;
            }
        }

        return -1;
    }

    buildTable(pattern) {
        const table = new Array(pattern.length).fill(0);
        let prefix = 0;

        for (let index = 1; index < pattern.length; index += 1) {
            while (prefix > 0 && pattern[index] !== pattern[prefix]) {
                prefix = table[prefix - 1];
            }

            if (pattern[index] === pattern[prefix]) {
                prefix += 1;
            }

            table[index] = prefix;
        }

        return table;
    }
}

Quick try

const text = 'ABABDABACDABABCABAB';
const matcher = new KmpMatcher('ABABCABAB');

console.log(matcher.table);
// [0, 0, 1, 2, 0, 1, 2, 3, 4]

console.log(matcher.search(text)); // [10]
console.log(matcher.indexOf(text)); // 10

const letters = new KmpMatcher('aa');
console.log(letters.search('aaa')); // [0, 1]

What it does

The table avoids comparing characters that are already known after a mismatch, so the time is linear in the text and pattern.
After a match it jumps by the table, so overlapping hits such as aa inside aaa are included.
An empty pattern returns []. indexOf returns -1 when nothing matches.

Where it fits

A practical place for this snippet in a real project.

Useful for finding a word in a long string in the UI or an analysis tool. It is not a search engine, and it does not replace an index.

Similar snippets

JAVASCRIPT

Binary Search Tree

Insert, search, and delete while keeping values sorted. Average O(log n), worst O(n) if the tree becomes a chain.

JAVASCRIPT

Function Memoization

Wrap a function and reuse its result for the same inputs. The next call with the same values skips the work.

JAVASCRIPT

LRU Cache

Keep a fixed number of entries and evict the least recently used item when the cache is full.

Need a snippet that is not here?

Describe the problem or idea, and I will see if it belongs in the library.

Contact me Library