createLPSArray.ts

function createLPSArray(w: string): number[] {
  const lps: number[] = [0];
  let len = 0;
  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]; // This is the big point!
      else lps[i++] = 0;
    }
  }
  return lps;
}