string-search • Advanced

Z-Algorithm: Linear Pattern Matching via Z-Array

The Z-Algorithm constructs a Z-array in O(N) time where Z[i] is the length of the longest substring starting from s[i] that is also a prefix of s, maintaining a rightmost matching window [L, R].

Intuitive Mental Model

The Laser Rangefinder: As you sweep along a wall, you remember the farthest point reached by your previous laser beam [L, R] to skip measuring overlapping sections.

C / TypeScript ImplementationHardware & Algorithmic Standard

function buildZArray(s: string): number[] {
  const n = s.length;
  const Z = new Array(n).fill(0);
  let L = 0, R = 0;

  for (let i = 1; i < n; i++) {
    if (i <= R) Z[i] = Math.min(R - i + 1, Z[i - L]);
    while (i + Z[i] < n && s[Z[i]] === s[i + Z[i]]) Z[i]++;
    if (i + Z[i] - 1 > R) {
      L = i;
      R = i + Z[i] - 1;
    }
  }
  return Z;
}

Key Architectural Takeaways

•Pattern Matching: Concatenate pattern + "$" + text and find indices where Z[i] == pattern.length.
•Strictly O(N) Execution: Inner while loop executes at most N total times across the entire algorithm.

Common Coding Mistake

Omitting a unique delimiter (like "$") when concatenating pattern and text.

Optimal Solution

Always use a character not present in the alphabet as a separator.

Next: Manacher's Algorithm: Longest Palindromic Substring in O(N)