Z-Algorithm String Matching: Efficient String Processing

1. Introduction and Core Concepts

Z-algorithm string matching is a linear-time pattern matching technique that belongs to the family of efficient string processing algorithms. Unlike naive approaches that repeatedly compare characters with backtracking, the Z-algorithm preprocesses a string to compute auxiliary information that allows it to skip redundant comparisons. At its heart, the algorithm computes a Z-array, where each entry Z[i] stores the length of the longest substring starting at position i that matches the prefix of the entire string. This simple yet powerful definition enables a wide range of string operations to be performed in optimal time.

The importance of z-algorithm string matching stems from its elegance and versatility. While many developers are familiar with Knuth-Morris-Pratt (KMP) or Boyer-Moore, the Z-algorithm offers an alternative that is often easier to understand and implement correctly. It requires no complex failure function or bad-character tables, only a single array and two pointers that maintain a sliding window known as the Z-box. This simplicity makes it an excellent teaching tool and a practical choice for production systems where code maintainability matters as much as performance.

Conceptually, z-algorithm string matching transforms the pattern searching problem into a prefix matching problem. To search for a pattern P in a text T, we construct a new string S = P + "$" + T, where "$" is a delimiter character that does not appear in either P or T. Computing the Z-array for S immediately reveals all occurrences of P in T: any position i where Z[i] equals the length of P corresponds to a perfect match. This reduction is what makes the algorithm so powerful, as a single linear scan of S solves the entire search problem without nested loops or backtracking.

What Is the Z-Array?

Formally, for a string S of length n, the Z-array Z is an array of length n where Z[0] is defined as 0 or n by convention, and for i greater than 0, Z[i] is the length of the longest prefix of S that is also a prefix of the suffix starting at i. For example, for S = "abacaba", Z[1] = 0 because "bacaba" does not start with "a", while Z[4] = 3 because "aba" matches the prefix "aba". This array encodes all prefix-suffix relationships in the string in a compact form.

Why Z-Algorithm Matters Today

In an era of massive text datasets, genomic sequences, log files, and real-time search systems, linear-time guarantees are not optional. A naive O(n * m) search can become prohibitively slow when searching for a 1,000-character pattern in a 10-million-character document. Z-algorithm string matching guarantees O(n + m) time regardless of input structure, with no pathological worst cases. Its deterministic performance, small memory footprint, and cache-friendly sequential access pattern make it highly suitable for modern hardware and large-scale data processing pipelines.

2. How It Works

The efficiency of z-algorithm string matching comes from its intelligent reuse of previously computed information. The algorithm maintains an interval [l, r] called the Z-box, which represents the interval with the maximum r such that S[l..r] matches the prefix of S. In other words, the substring from l to r is a prefix of S, and r is as far to the right as we have matched so far. This window acts as a memory of the furthest successful prefix match, allowing future positions to be answered in constant time when possible.

When computing Z[i] for a new position i, there are two distinct cases. If i lies outside the current Z-box (i greater than r), no prior information can help, and the algorithm resorts to naive character-by-character comparison starting from S[0] and S[i]. This is the slow path, but it also expands the Z-box when a match is found, which will benefit subsequent positions. If i lies inside the Z-box (i less than or equal to r), we know that S[i..r] matches S[i-l..r-l] because both are inside the same prefix match. Therefore, Z[i] is at least min(Z[i-l], r - i + 1), and we may not need to compare at all.

This second case is the key optimization. The value Z[i-l] is already known, and it tells us how far the prefix matches at the mirrored position i-l. If Z[i-l] is less than the remaining length of the Z-box (r - i + 1), then we know Z[i] equals Z[i-l] exactly, with no further comparisons needed. If Z[i-l] is greater than or equal to the remaining length, then the prefix match might extend beyond r, so we need to attempt to extend it by comparing characters beyond r. In either subcase, each successful comparison increases r, and r only moves forward across the entire execution.

The Z-Box Invariant

The invariant that makes the algorithm correct is that [l, r] is always the interval with the maximum r among all intervals starting at or before the current i. Maintaining this invariant is simple: after computing Z[i], if i + Z[i] - 1 is greater than r, we set l = i and r = i + Z[i] - 1. This ensures the box always represents the rightmost prefix match discovered so far. Because r never decreases, the total number of character comparisons that increase r is bounded by n, which is the foundation of the linear time proof.

Intuition Through Prefix Reuse

Consider searching for "abc" in "abcabcabc". After computing Z values for the prefix "abc", the algorithm recognizes that the substring starting at position 3 is identical to the prefix, so it can copy the answer without work. This is similar to how a human would scan text: once you know a section repeats, you do not re-read it character by character. The Z-algorithm formalizes this intuition into a precise, provably optimal procedure that avoids the redundant work that cripples naive search.

3. Implementation

Implementing z-algorithm string matching in Python is straightforward and requires only basic array manipulation. The core routine computes the Z-array in a single pass, while a wrapper function handles the pattern-plus-text concatenation for searching. Below are four progressively more complete implementations that illustrate both the basic mechanism and practical considerations for production use.

The first implementation is the canonical Z-function. It takes a single string and returns its Z-array. Note the careful handling of the Z-box boundaries and the min operation that prevents unnecessary comparisons. This version is the building block for all other applications.

def compute_z_array(s):
    n = len(s)
    z = [0] * n
    l = 0
    r = 0
    # z[0] is defined as 0 for convenience (some definitions use n)
    for i in range(1, n):
        if i <= r:
            # Inside current Z-box, reuse previously computed value
            z[i] = min(r - i + 1, z[i - l])
        # Explicitly extend match beyond current box
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        # Update Z-box boundaries if we extended beyond r
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

# Quick test
print(compute_z_array("abacaba"))  # [0, 0, 1, 0, 3, 0, 1]
print(compute_z_array("aaaaa"))    # [0, 4, 3, 2, 1]

The second implementation shows how to use the Z-array for exact pattern matching. The choice of separator is critical: it must be a character guaranteed not to appear in either the pattern or the text. In practice, for general Unicode text, you may need to choose a multi-character separator or verify that the chosen character is absent. For DNA sequences, "$" is safe; for natural language, a null character or a character outside the expected alphabet is preferable.

def z_search(text, pattern):
    # Concatenate pattern + separator + text
    # Separator should be a character not in either string
    concat = pattern + "$" + text
    z = compute_z_array(concat)
    pattern_len = len(pattern)
    occurrences = []
    for i in range(pattern_len + 1, len(concat)):
        if z[i] == pattern_len:
            # Match found, convert to text index
            text_index = i - pattern_len - 1
            occurrences.append(text_index)
        # For partial matches: z[i] > 0 indicates prefix match length
        # Could be used for approximate matching diagnostics
    return occurrences

# Example usage
text = "abacabadabacaba"
pattern = "aba"
print(z_search(text, pattern))  # Output: [0, 4, 8, 12]

The third example demonstrates ancillary uses of the Z-array beyond simple search. Many string problems reduce to analyzing prefix occurrences, such as finding the longest prefix that appears elsewhere, enumerating all borders, or computing repetition structure. These utilities show why computing the Z-array is valuable even when you are not searching for an external pattern.

def find_all_prefix_matches(s):
    z = compute_z_array(s)
    result = []
    for i in range(1, len(s)):
        if z[i] > 0:
            # s[0:z[i]] == s[i:i+z[i]]
            result.append((i, z[i], s[i:i+z[i]]))
    return result

def longest_prefix_occurrence(s):
    # Find longest prefix that appears elsewhere in string
    z = compute_z_array(s)
    max_len = 0
    max_pos = -1
    for i in range(1, len(z)):
        if z[i] > max_len:
            max_len = z[i]
            max_pos = i
    return max_pos, max_len

s = "abacaba"
print(find_all_prefix_matches(s))
# [(1, 0?) ... actual: (4, 3, 'aba'), (6, 1, 'a')]
print(longest_prefix_occurrence(s))  # (4, 3)

The final implementation is an optimized, production-ready version that handles edge cases, avoids unnecessary string copying for very large inputs, and includes early exits. It also demonstrates how to integrate the Z-computation and matching loop to avoid a second pass over the array, which can improve cache locality for huge texts.

def z_algorithm_optimized(text, pattern):
    # Optimized for large texts: avoids building huge concat twice
    m = len(pattern)
    n = len(text)
    # Edge cases
    if m == 0 or m > n:
        return []
    # Use separator not in alphabet
    combined = pattern + "#" + text
    total_len = len(combined)
    z = [0] * total_len
    l = r = 0
    matches = []
    for i in range(1, total_len):
        if i <= r:
            z[i] = min(r - i + 1, z[i - l])
        while i + z[i] < total_len and combined[z[i]] == combined[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
        # Check for full pattern match (only in text part)
        if i > m and z[i] >= m:
            matches.append(i - m - 1)
    return matches

# Performance test helper
import time
def benchmark():
    text = "a" * 1000000 + "b"
    pattern = "a" * 500 + "b"
    start = time.time()
    res = z_algorithm_optimized(text, pattern)
    elapsed = time.time() - start
    print(f"Found {len(res)} matches in {elapsed:.4f}s")

4. Step-by-Step Example

To make the abstract mechanism concrete, let us walk through z-algorithm string matching on the string S = "abacaba". We will compute its Z-array step by step, tracking the Z-box [l, r] and the decisions made at each position. This example illustrates both the naive comparison path and the optimization path where values are copied.

We initialize Z[0] = 0, l = 0, r = 0. For i = 1, S[1] = 'b' versus S[0] = 'a' mismatch immediately, so Z[1] = 0. Since i + Z[i] - 1 = 0 is not greater than r = 0, the box remains [0, 0]. For i = 2, S[2] = 'a' matches S[0] = 'a', and S[3] = 'c' versus S[1] = 'b' mismatches, so Z[2] = 1. Now i + Z[i] - 1 = 2, which is greater than r, so we update l = 2, r = 2. The Z-box now covers the single-character prefix match at position 2.

For i = 3, i = 3 is greater than r = 2, so we are outside the box and must compare naively. S[3] = 'c' versus S[0] = 'a' mismatches, so Z[3] = 0 and the box does not change. For i = 4, i = 4 is also outside the box (4 greater than 2), so we compare naively: S[4] = 'a' matches S[0] = 'a', S[5] = 'b' matches S[1] = 'b', S[6] = 'a' matches S[2] = 'a', and we hit the end of the string. Thus Z[4] = 3, and we update l = 4, r = 6. This is the longest prefix occurrence in this string.

Continuing the Walkthrough

For i = 5, we are now inside the box [4, 6]. We compute i - l = 1, and Z[1] = 0. The remaining box length is r - i + 1 = 2. So min(Z[1], 2) = 0, we set Z[5] = 0 initially and try to extend beyond r. Comparing S[0] = 'a' versus S[5] = 'b' mismatches, so Z[5] stays 0. No box update occurs because i + Z[i] - 1 = 4 is not greater than 6.

For i = 6, we are still inside the box. Here i - l = 2, Z[2] = 1, and r - i + 1 = 1. So min(1, 1) = 1, we set Z[6] = 1. We then try to extend: i + Z[i] = 7 equals n, so we stop. Since Z[2] was not less than the remaining length, we did attempt an extension but found no further match. The final Z-array is [0, 0, 1, 0, 3, 0, 1], which correctly encodes all prefix matches.

Applying to Pattern Search

Now consider searching for P = "aba" in T = "abacaba". We build S = "aba$abacaba" (length 11). Computing Z for S yields matches where Z[i] = 3. At i = 4 (the start of T), Z[4] = 3, indicating a match at text position 0. At i = 8, Z[8] = 3, indicating a match at text position 4. The algorithm finds both occurrences in a single linear scan, without ever backtracking in T. This walkthrough shows how the prefix-centric view of the Z-array directly solves the substring search problem.

5. Complexity Analysis

The theoretical appeal of z-algorithm string matching lies in its guaranteed linear time complexity, which holds for all inputs regardless of structure. Unlike algorithms whose performance depends on alphabet size or pattern characteristics, the Z-algorithm's running time is strictly proportional to the length of the processed string. This predictability is crucial for systems that must handle adversarial or worst-case inputs without degradation.

Time complexity is O(n) for building the Z-array of a string of length n, and O(n + m) for searching for a pattern of length m in a text of length n, where the combined string length is n + m + 1. The proof relies on the monotonic increase of r. Each iteration of the inner while loop that succeeds increments r by one, and r never decreases and never exceeds n - 1. Therefore, the total number of successful character comparisons across the entire algorithm is at most n. Failed comparisons occur at most once per position i, adding another O(n) bound. Together, this yields linear time.

Space complexity is O(n) for the Z-array itself, plus O(n + m) for the concatenated string if you explicitly construct it. In memory-constrained environments, it is possible to compute Z values on the fly without storing the entire concatenated string, by treating the pattern and text as two separate regions and mapping indices accordingly. However, the Z-array itself is generally required for the algorithm's logic and cannot be avoided without sacrificing the linear time guarantee.

It is worth noting that best, average, and worst cases are identical for the Z-algorithm: all are linear. This is a strong advantage over algorithms like Boyer-Moore, which can degrade to O(n * m) in the worst case, or naive search which is quadratic in the worst case. The constant factors for the Z-algorithm are also small, as the inner loop is tight and the memory access pattern is sequential, leading to excellent cache performance on modern CPUs. For most practical purposes, the algorithm is as fast as theoretically possible for exact string matching.

Amortized Analysis Insight

The amortized analysis hinges on the fact that each character of S is compared at most twice: once as part of an extension that increases r, and once as a failed comparison that terminates an extension. This double-counting argument is a classic example of amortized complexity, where expensive operations (long extensions) are rare and cheap operations (copied values) are frequent. Understanding this proof is essential for appreciating why the algorithm never revisits characters unnecessarily and why it outperforms naive methods by such a large margin on repetitive texts.

6. Variations and Optimizations

While the classic Z-algorithm is already optimal in asymptotic terms, several variations and optimizations adapt it to specific use cases, improve constant factors, or extend its functionality. These enhancements are important when deploying z-algorithm string matching in performance-critical systems or when solving problems beyond simple exact matching.

One common optimization is the in-place or streaming Z-algorithm, which avoids constructing the concatenated string S = P + "$" + T explicitly. Instead, it treats the pattern and text as separate buffers and computes Z values by mapping indices to the appropriate buffer. This reduces memory allocation overhead and improves locality when the text is extremely large or arrives as a stream. For example, when processing network packets or log files that do not fit in memory, a streaming variant can process chunks incrementally while maintaining the Z-box state across chunk boundaries.

Another variation is the modified Z-algorithm for alphabet-independent matching. The standard algorithm assumes exact character equality, but many applications require case-insensitive matching, wildcard support, or approximate matching with a tolerance for mismatches. By replacing the equality check s[z[i]] == s[i + z[i]] with a custom predicate, such as casefold equality or a wildcard match, the same Z-box logic can be reused for more flexible search semantics without changing the overall structure.

Advanced Variants

Researchers have developed a Z-algorithm for parameterized pattern matching, where the alphabet is divided into static and parameterized symbols. This is useful for detecting code clones or plagiarism, where variable names may be renamed but the structure remains identical. Another variant computes the Z-array for multiple patterns simultaneously by building a combined structure similar to Aho-Corasick but using Z-box principles for linear-time multi-pattern search.

For highly repetitive strings, such as those found in bioinformatics, an optimization known as Z-algorithm with prefix hashing can accelerate the extension step. Instead of comparing characters one by one beyond the Z-box, it uses rolling hashes to compare blocks of characters in constant time, falling back to character comparison only when hashes match. This can reduce the number of character comparisons in practice, though it does not improve worst-case asymptotic complexity and introduces a small risk of hash collisions if not verified.

Choosing the right variant depends on the problem constraints. For most web and database applications, the classic implementation is sufficient and preferred for its simplicity. For specialized domains like genomics or cybersecurity, the more advanced variants can provide significant practical speedups or enable functionality that the basic algorithm cannot support. The key is to preserve the core Z-box invariant while adapting the comparison logic to the domain.

7. Real-World Applications

Z-algorithm string matching is not merely an academic exercise; it powers numerous real-world systems where efficient text processing is critical. Its linear-time guarantee and simple implementation make it a go-to choice for developers building search features, data processing pipelines, and network services that must handle unpredictable input sizes without performance cliffs.

In web servers and search engines, the Z-algorithm is used for URL routing, template matching, and query processing. When a web framework needs to match incoming request paths against a large set of route patterns, a Z-based approach can quickly identify prefix matches and parameter boundaries. Similarly, in full-text search indexing, the algorithm helps identify term occurrences and phrase boundaries during document tokenization, especially when combined with suffix array construction where Z-values are used to compute longest common prefixes efficiently.

Databases leverage z-algorithm string matching for substring search, pattern indexing, and query optimization. SQL LIKE queries with prefix patterns, regular expression pre-filtering, and even B-tree key comparisons can benefit from Z-array preprocessing. In columnar databases that store large string columns, the algorithm enables fast filtering without decompressing entire columns, as the Z-box can skip over non-matching regions. Some database engines use Z-like techniques to accelerate string similarity joins and deduplication tasks.

Networking and Security

In networking, deep packet inspection (DPI) and intrusion detection systems (IDS) must scan packet payloads for thousands of attack signatures at line speed. While Aho-Corasick is common for multi-pattern matching, the Z-algorithm is often used as a fast pre-filter or for single-pattern signature matching where its low overhead shines. It is also used in data compression algorithms, such as those based on LZ77, where finding the longest prefix match is the core operation for identifying repeated substrings to encode.

Bioinformatics and Data Science

Perhaps the most demanding application is bioinformatics, where researchers search for gene patterns, motifs, and tandem repeats in DNA sequences that can be billions of characters long. The Z-algorithm's linear time and ability to find all prefix occurrences make it ideal for genome assembly, sequence alignment preprocessing, and finding palindromic structures. In data science, it is used for log analysis, plagiarism detection, and natural language processing tasks like finding the longest repeated substring or computing string periodicity for feature extraction.

These examples illustrate that z-algorithm string matching is a versatile tool that appears wherever string processing performance matters. Its combination of theoretical optimality and practical simplicity ensures it remains relevant even as newer algorithms emerge, particularly in systems where code clarity and predictable latency are valued alongside raw speed.

8. Comparison with Alternatives

Choosing the right string matching algorithm requires understanding the trade-offs between time complexity, space usage, preprocessing cost, and implementation complexity. While z-algorithm string matching is an excellent general-purpose choice, it is not always the best option for every scenario. Comparing it with other classic algorithms helps clarify when to use each approach.

The naive algorithm, which checks every position in the text by comparing the pattern character by character, is simple to implement but has O(n * m) worst-case time. It is only suitable for very small texts or when the pattern is guaranteed not to cause many partial matches. Knuth-Morris-Pratt (KMP) also achieves O(n + m) time and O(m) space by preprocessing the pattern to build a failure function that indicates where to resume matching after a mismatch. KMP is similar to the Z-algorithm in guarantees but is often considered slightly more complex to implement correctly due to the prefix function logic.

Boyer-Moore is a family of algorithms that can achieve sublinear time on average by skipping characters using bad-character and good-suffix heuristics. It excels when the alphabet is large and the pattern is long, as it can jump ahead many positions after a mismatch. However, its worst-case time is O(n * m) without additional modifications, and its implementation is significantly more complex. Rabin-Karp uses hashing to compare pattern and text windows in constant time, achieving O(n + m) average time but O(n * m) worst case due to hash collisions, and it requires careful handling of hash functions and modulus operations.

In practice, the Z-algorithm and KMP are often interchangeable for single-pattern exact matching, with the choice coming down to personal preference and the specific problem variant. The Z-algorithm has a slight edge when the problem is naturally expressed in terms of prefix matches, such as finding the longest prefix that appears elsewhere, computing string periods, or building suffix arrays. KMP has a slight edge in streaming scenarios where the text arrives character by character and you cannot afford to store the entire concatenated string, as its O(m) space is smaller than the Z-algorithm's O(n + m).

Boyer-Moore remains the champion for searching long patterns in natural language text where mismatches are frequent and large skips are possible. Rabin-Karp shines for multi-pattern search and for problems where hashing can be reused, such as finding duplicate substrings. For most interview and production scenarios involving exact matching with moderate pattern and text sizes, z-algorithm string matching offers the best balance of performance, simplicity, and reliability.

9. Common Mistakes and Best Practices

Even though z-algorithm string matching is conceptually simple, several common pitfalls can lead to incorrect results, performance degradation, or subtle bugs that are hard to diagnose. Awareness of these mistakes and adherence to best practices will help ensure your implementation is both correct and efficient.

One frequent mistake is choosing an inappropriate separator character when concatenating pattern and text. If the separator appears in either string, the Z-values can incorrectly span the boundary, leading to false matches or missed matches. For example, using "$" when the text itself contains "$" will corrupt the Z-array. The best practice is to either verify that the separator is absent, use a character outside the input alphabet such as a null byte or a Unicode private-use character, or avoid concatenation altogether by implementing a virtual concatenation that checks bounds without building a new string.

Another common error is mishandling the Z-box update logic. Developers sometimes forget to take the minimum of Z[i-l] and r - i + 1 when inside the box, or they incorrectly update l and r even when no extension occurred. This can cause the algorithm to either miss matches or degrade to quadratic time. The correct logic is to initialize Z[i] to min(r - i + 1, Z[i - l]) only when i is inside the box, then attempt to extend, and only update l and r if i + Z[i] - 1 is strictly greater than r. Off-by-one errors in these indices are extremely common and should be tested with edge cases like "aaaaa" and "abacaba".

A third pitfall is defining Z[0] inconsistently. Some definitions set Z[0] = n, others set Z[0] = 0. While this does not affect pattern search when you ignore Z[0], it can cause confusion when the Z-array is used for other purposes like computing the longest prefix occurrence or string periodicity. Document your convention clearly and ensure all downstream code respects it. Similarly, failing to handle empty pattern or empty text edge cases can cause index errors or infinite loops.

Best Practices for Production Code

• Validate inputs: Check for empty strings, None values, and separator collisions before processing. Return early for trivial cases like empty pattern or pattern longer than text.
• Use 0-based indexing consistently: Python's 0-based indexing aligns well with the Z-algorithm, but translating from 1-based pseudocode often introduces off-by-one bugs. Test with small strings where you can manually compute expected Z-values.
• Prefer iterative over recursive: The Z-algorithm is inherently iterative. Avoid recursion which adds overhead and risks stack overflow for large strings.
• Profile before optimizing: The classic implementation is already linear. Only introduce block-hashing or streaming variants if profiling shows that string concatenation or character comparison is a bottleneck for your specific workload.
• Write comprehensive tests: Include tests for repetitive strings ("aaaaa"), no-match cases ("abc" in "def"), overlapping matches ("aa" in "aaa"), and large random strings compared against naive search for correctness.

Finally, remember that z-algorithm string matching is not a silver bullet for all string problems. For approximate matching with edit distance, for regular expression matching, or for searching with wildcards that require backtracking, other algorithms like dynamic programming or automata-based methods are more appropriate. Use the Z-algorithm when the problem reduces to exact prefix matching, and choose a different tool when the problem semantics differ.

10. Interview Questions

Z-algorithm string matching is a favorite topic in technical interviews for roles involving algorithms, backend engineering, or data processing. Interviewers use it to assess understanding of linear-time string processing, amortized analysis, and the ability to adapt a core algorithm to related problems. Below are common questions and guidance on how to approach them effectively.

Question 1: Implement the Z-function and Use It to Find Pattern Occurrences

This is the most direct question: given a text and pattern, find all occurrences using the Z-algorithm. The expected solution is to implement compute_z_array as shown earlier and then search in S = pattern + "$" + text. Interviewers look for correct handling of the Z-box, proper separator choice, and conversion of Z-indices back to text indices. Be prepared to explain why the separator is necessary and what happens if it is omitted. Time complexity should be stated as O(n + m) and space as O(n + m), with a clear explanation of why r only moves forward.

Question 2: How Does the Z-Algorithm Achieve Linear Time? Prove It.

Here the interviewer wants the amortized analysis. Explain that r is monotonic and each successful character comparison increments r, so there are at most n successful comparisons. Failed comparisons happen at most once per i, so total comparisons are O(n). Contrast this with naive search where the same characters are compared repeatedly. A strong answer will walk through the two cases (inside vs outside Z-box) and show how the min operation avoids redundant work. Mentioning that best, average, and worst cases are all linear demonstrates deeper understanding.

Question 3: Find the Longest Prefix That Also Appears Elsewhere in the String

Given a string S, find the longest prefix that occurs at least once more in S. This tests whether you understand that the Z-array already encodes this information: the answer is simply max(Z[i]) for i greater than 0, and the position is argmax. Discuss edge cases like no repetition (answer 0) and overlapping occurrences. An extension is to find all prefixes that appear elsewhere, which is the set of i where Z[i] greater than 0, or to find the longest prefix that appears at least k times.

Question 4: Compare Z-Algorithm with KMP — When Would You Prefer One Over the Other?

This question evaluates system design judgment. Explain that both are O(n + m) and both avoid backtracking, but Z-algorithm is often simpler to code and more natural for prefix-related problems, while KMP uses O(m) extra space versus O(n + m) and is better for streaming where text arrives incrementally. Mention Boyer-Moore as a contrast for large alphabets and long patterns. A good answer includes a table of trade-offs and states that for most interview problems either is acceptable, but you should be able to implement one flawlessly.

Question 5: How Would You Modify the Z-Algorithm to Handle Wildcards or Case-Insensitive Search?

This tests adaptability. The core idea is to replace the equality check s[z[i]] == s[i + z[i]] with a custom matcher function, such as case-insensitive comparison or wildcard logic where '?' matches any character. Explain that the Z-box logic remains unchanged because it only depends on the length of the match, not the comparison semantics. Discuss potential pitfalls, like wildcards breaking the prefix equivalence assumption if not handled carefully, and how to test such modifications. This shows you can generalize the algorithm beyond its textbook form.

Preparing for these questions involves not just memorizing code, but understanding the invariants, being able to walk through examples on a whiteboard, and articulating complexity trade-offs. Practice implementing the Z-function from scratch without referencing material, and test it on diverse inputs to build confidence. Mastery of z-algorithm string matching signals strong algorithmic fundamentals that interviewers highly value.