GeezerVison is showing github.com — failure-function/src/build.js at main · string-data-structure/failure-function

Expand file tree

build.js

Copy path

More file actions

Latest commit

History

50 lines (45 loc) · 977 Bytes

build.js

Copy path

File metadata and controls

50 lines (45 loc) · 977 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

/**

* Computes the failure function for input string.

* This is the "next[j]" table found in

* "Fast pattern matching in strings" by Knuth, Morris, and Pratt,

* although here indices are 0-based hence all indices and inputs are one less

* than in that paper.

* NOTE The main loop is somewhat unrolled for faster execution. This was not

* benchmarked.

* @param {ArrayLike} p

* @param {number} pi

* @param {number} pj

* @param {number[]} t

* @param {number} ti

const build = (p, pi, pj, t, ti) => {

t[ti] = -1;

if (pi === pj) return;

const p0 = pi;

if (++pi === pj) {

t[++ti] = 0;

return;

}

const t0 = ti;

t[++ti] = p[pi] === p[p0] ? -1 : 0;

let m = 0;

--pj;

while (pi < pj) {

while (p[pi] !== p[p0 + m]) {

m = t[t0 + m];

if (m === -1) break;

}

++m;

t[++ti] = p[++pi] === p[p0 + m] ? t[t0 + m] : m;

}

while (p[pj] !== p[p0 + m]) {

m = t[t0 + m];

if (m === -1) break;

}

++m;

t[++ti] = m;

};

export default build;