Sample implementation for KMP Match algorithm

kmpMatch.js

function computeLpsArray(pat) {
  let len = 0;
  let i = 1;
  const lps = [];
  lps[0] = 0;

  while (i < pat.length) {
    if (pat.charAt(i) === pat.charAt(len)) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len != 0) {
        len = lps[len - 1];
      } else {
        lps[i] = len;
        i++;
      }
    }
  }

  return lps;
}

function kmpMatch(pat, txt) {
  const lps = computeLpsArray(pat);
  let i = 0;
  let j = 0;

  while (i < txt.length) {
    if (pat.charAt(j) === txt.charAt(i)) {
      i++;
      j++;
    }
    if (j === pat.length) {
      console.log("Found pattern at index " + (i -j));
      j = lps[j - 1];
    } else if (i < txt.length && pat.charAt(j) !== txt.charAt(i)) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
}