🧻 @string-searching/matiyasevich-knuth-morris-pratt

Knuth-Morris-Pratt algorithm for JavaScript. See docs.

⚠️ 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';