Problem Overview & Intuition

The Longest Prefix Suffix (LPS) array allows KMP to avoid re-examining characters upon mismatch. By falling back to len = lps[len - 1] rather than resetting to 0, construction runs in linear O(N) time.

Step-by-Step Approach

1. Initialize lps = new Array(n).fill(0), len = 0, and i = 1.
2. While i < n:
3. If pattern[i] === pattern[len]: len++, lps[i] = len, i++.
4. Else if len !== 0: fall back len = lps[len - 1] without incrementing i.
5. Else: lps[i] = 0, i++.
6. Return lps.

Optimal Implementation (JavaScript)

function computeLPSArray(pattern) {
  const n = pattern.length;
  const lps = new Array(n).fill(0);
  let len = 0, i = 1;
  while (i < n) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return lps;
}

Complexity Analysis