Visit https://yuji.page/kmp-algorithm/ for more information.

KMPSearch.ts

export function KMPsearch(s: string, w: string): number[] {
  const acc: number[] = [];
  const LPS: number[] = createLPSArray(w);
  let [i, j] = [0, 0];
  while (i < s.length) {
    if (s[i] === w[j]) {
      i += 1;
      j += 1;
      if(j === w.length) {
        acc.push(i-j);
        j = LPS[j-1];
      }
    } else {
      if (j === 0) i += 1;
      else j = LPS[j-1]
    }
  }
  return acc;
}

function createLPSArray(w: string): number[] {
  const lps: number[] = [0];
  let len = 0; // The last item of lps.
  let i = 1;
  while (i < w.length) {
    if (w.charAt(i) === w.charAt(len)) {
      lps.push(++len);
      i++;
    } else {
      if (len !== 0) len = lps[len-1]; // Refer to the proof!
      else lps[i++] = 0;
    }
  }
  return lps;
}