Z Algorithm Explained: Linear-Time Pattern Matching Using the Z-Box Technique

The Z Algorithm is a string-matching method that finds all occurrences of a pattern within a text in O(N) linear time. It works by maintaining a Z-Box, a window [L, R] representing a substring already known to match the string's prefix, which helps avoid redundant character comparisons. For each index, the algorithm either reuses previously computed values if the index falls within the Z-Box or starts fresh comparisons if it falls outside. This approach reduces the naive O(N²) brute-force complexity to O(N) time with O(N) space. The algorithm is commonly referenced in coding interviews as an efficient solution for prefix-based pattern matching problems.