: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';