@string-searching/matiyasevich-knuth-morris-pratt
v1.0.0
Published
Knuth-Morris-Pratt algorithm for JavaScript
Downloads
16
Readme
:roll_of_paper: @string-searching/matiyasevich-knuth-morris-pratt
Knuth-Morris-Pratt algorithm for JavaScript. See docs.
:warning: Depending on your environment, the code may require
regeneratorRuntime
to be defined, for instance by importing regenerator-runtime/runtime.
// Compile a fast string/array searching function as follows.
import {build as _failureFunction} from '@string-data-structure/failure-function';
const ff = (p, pi, pj) => {
const next = new Array(pj - pi + 1);
_failureFunction(p, pi, pj, next, 0);
return next;
};
import {fastScan} from '@string-searching/matiyasevich-knuth-morris-pratt';
const _findAll = (s, si, sj, p, pi, pj) => {
assert(sj - si >= 2); // NOTE Use different methods if your
assert(pj - pi >= 2); // inputs are that small.
const t = ff(p, pi, pj);
return fastScan(p, pi, pj, t, 0, s, si, sj);
};
const findAll = (text, pattern) =>
_findAll(text, 0, text.length, pattern, 0, pattern.length);
for (const i of findAll('abracadabra', 'abra')) ... // yields 0 7
for (const i of findAll([0, 1, 1, 0, 1, 0, 0, 0], [0, 0])) ... // yields 5 6
// There is also an implementation that has a lower code footprint and handles
// all input sizes >= 1. This implementation is a constant factor slower but
// has the same worst-case linear-time guarantee.
import {lessCode} from '@string-searching/matiyasevich-knuth-morris-pratt';