Knuth–Morris–Pratt algorithm that works with JS Array & TypedArray
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src
test
.gitignore
LICENSE
README.md
package-lock.json
package.json

README.md

Knuth–Morris–Pratt Search

An naive implementation of Knuth–Morris–Pratt algorithm that works with Array & TypedArray

Installation

npm install git+https://github.com/Chocobo1/kmps.git

Usage example

const Kmp = require('kmps');  // import this module

// working with TypedArray
{
    const pattern = Uint32Array.from([0xFFFF, 0x3000]);
    const corpus = Uint32Array.from([0xFFFF, 0xFFFF, 0x3000, 0x1000]);

    // setup `kmp` for later reuse
    const kmp = Kmp.KnuthMorrisPratt(pattern);
    // returns the first index of the exact match in `corpus`; -1 if not found
    const idx = kmp.match(corpus);
    if (idx !== 1)
        throw (new Error('Please file an issue'));
}

// also working with String
{
    const pattern = "pattern";
    const corpus = "some pattern !@#$%";

    const kmp = Kmp.KnuthMorrisPratt(pattern);
    const idx = kmp.match(corpus);
    if (idx !== corpus.indexOf(pattern))
        throw (new Error('Please file an issue'));
}

// you can specify offset!
{
    const pattern = "123";
    const corpus = "123abc123";
    const corpusOffset = 1;

    const idx = Kmp.KnuthMorrisPratt(pattern).match(corpus, corpusOffset);
    if (idx !== corpus.indexOf(pattern, corpusOffset))
        throw (new Error('Please file an issue'));
}

Run tests

npm install -D  # install dev dependencies
npm test        # run tests

References

See also

You might be interested to Boyer–Moore–Horspool algorithm

License

See LICENSE file