An naive implementation of Knuth–Morris–Pratt algorithm that works with Array & TypedArray
npm install git+https://github.com/Chocobo1/kmps.gitconst Kmp = require('kmps'); // import this module, CommonJS style //import * as Kmp from 'kmps'; // import this module, ES module style // 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')); }npm install -D # install dev dependencies npm test # run tests- https://www.inf.hs-flensburg.de/lang/algorithmen/pattern/kmpen.htm
- https://people.ok.ubc.ca/ylucet/DS/KnuthMorrisPratt.html
You might be interested to Boyer–Moore–Horspool algorithm
See LICENSE file