KMP string search algorithm

kmp.js

function buildNext(pattern = '') {
  const next = (new Array(pattern.length + 1)).fill(0)
  let i = 0;
  let j = 1

  while (j < pattern.length) {
    if(pattern[i] === pattern[j]) {
      i++
      j++
      next[j] = i
    } else if (i === 0) {
      j++
    } else {
      i = next[i];
    }
  }
  
  return next;
}

function kmpIndexOf(text, pattern) {
  const next = buildNext(pattern);
  let j = 0;

  for(let i = 0; i < text.length; i++) {
    while(j > 0 && text[i] !== pattern[j]) { // Use common-prefix-suffix length to skip positions as more as possible.
      j = next[j]
    }

    if(text[i] === pattern[j]) {
      j++
    }

    if (j === pattern.length) {
      return i - pattern.length + 1
    }
  }

  return -1
}

function kmpFindAll(text, pattern) {
  const next = buildNext(pattern);
  const ans = [];
  let j = 0;

  for(let i = 0; i < text.length; i++) {
    while(j > 0 && text[i] !== pattern[j]) {  // Use common-prefix-suffix length to skip positions as more as possible.
      j = next[j]
    }

    if(text[i] === pattern[j]) {
      j++
    }

    if (j === pattern.length) {
      ans.push(i - pattern.length + 1)
      j = next[j] // pretend mismatch here for further searching
    }
  }

  return ans
}

const pattern = 'ABA'
const text = 'ABC ABABA ABABABACDABCDABDE'
console.log(kmpFindAll(text, pattern).map(idx => text.substr(idx, pattern.length)));