{"title":"Chapter 5: Z-Algorithm","description":"","content":"# Chapter 5: Z-Algorithm\n\nThe Z-Algorithm does something that sounds almost too simple to be powerful: for every position in a string, it computes the length of the longest substring starting at that position that matches a prefix of the string. This single piece of information, stored in what we call the Z-array, turns out to solve pattern matching, string period detection, and several other problems in linear time.\n\nWhat makes the Z-Algorithm special is its directness. KMP builds a failure function that requires careful reasoning about borders. Rabin-Karp relies on hash functions and deals with collisions. The Z-Algorithm, by contrast, asks a straightforward question at each position, \"how much of the beginning of this string do I see again right here?\", and the answer to that question is immediately useful.\n\nLet us start by understanding exactly what the Z-array is.\n\n---\n\n## What Is the Z-Array?\n\nGiven a string S of length n, the Z-array is an array Z of the same length where Z[i] stores the length of the longest substring starting at position i that matches a prefix of S. In other words, Z[i] is the length of the longest common prefix between S and the suffix of S starting at position i.\n\nBy convention, Z[0] is undefined (or set to 0) because the entire string trivially matches its own prefix. Some implementations set Z[0] = n, but most algorithms skip position 0 entirely.\n\nLet us compute the Z-array for a concrete example.\n\n**Example: S = \"aabxaab\"**\n\n\n```shell\nIndex: 0 1 2 3 4 5 6\nString: a a b x a a b\nZ-array: - 1 0 0 3 1 0\n```\n\n\nHere is how we get each value:\n\n- **Z[1] = 1**: Starting at index 1, the substring \"abxaab\" shares a prefix of length 1 with \"aabxaab\" (just \"a\").\n- **Z[2] = 0**: Starting at index 2, the substring \"bxaab\" does not match the prefix \"a...\" at all.\n- **Z[3] = 0**: Starting at index 3, \"xaab\" does not match the prefix either.\n- **Z[4] = 3**: Starting at index 4, the substring \"aab\" matches the prefix \"aab\" for 3 characters.\n- **Z[5] = 1**: Starting at index 5, \"ab\" matches the prefix \"a\" for 1 character.\n- **Z[6] = 0**: Starting at index 6, \"b\" does not match the prefix \"a\".\n\n\n```mermaid\nflowchart LR\n subgraph String[\"S = aabxaab\"]\n direction LR\n S0[\"a
Z=−\"]:::cyan\n S1[\"a
Z=1\"]:::green\n S2[\"b
Z=0\"]:::cyan\n S3[\"x
Z=0\"]:::cyan\n S4[\"a
Z=3\"]:::green\n S5[\"a
Z=1\"]:::green\n S6[\"b
Z=0\"]:::cyan\n end\n\n P1[\"Prefix match:
S[4..6] = aab
= S[0..2]\"]:::orange\n\n S4 -.-> P1\n\n classDef cyan fill:#00ceff,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\nThe green-highlighted positions are where Z[i] > 0, meaning those positions match some prefix of the string. Notice that Z[4] = 3 tells us \"the substring starting at index 4 matches the first 3 characters of the string.\" This is exactly the kind of information we need for pattern matching.\n\n**Interview Insight:** The Z-array captures prefix-matching information in a way that is arguably more intuitive than KMP's failure function. While the failure function tells you \"where to continue after a mismatch,\" the Z-array directly tells you \"how long of a prefix match exists here.\" Both encode the same structural information about the string, but the Z-array is easier to reason about.\n\n---\n\n## The Naive Approach vs. the Z-Box Optimization\n\nThe straightforward way to compute the Z-array is to check each position independently. For every index i from 1 to n-1, start comparing S[i], S[i+1], S[i+2], ... against S[0], S[1], S[2], ... until there is a mismatch.\n\n\n```shell\nNaive Z-array computation:\nFor i = 1 to n-1:\n Z[i] = 0\n while i + Z[i] < n and S[Z[i]] == S[i + Z[i]]:\n Z[i] += 1\n```\n\n\nThis works, but in the worst case it is O(n^2). Consider a string like \"aaaaaaa\". For every position i, the inner loop runs all the way to the end of the string.\n\nThe key insight that brings us to O(n) is called the **Z-box** (sometimes called the Z-window). The idea is similar in spirit to what Manacher's algorithm does for palindromes: we maintain a window of already-matched characters and reuse that information to avoid redundant comparisons.\n\n### The Z-Box [L, R]\n\nAt any point during the algorithm, we track the interval [L, R] where R is the rightmost position reached by any previous Z-box. Formally, [L, R] is the rightmost interval such that S[L..R] matches S[0..R-L]. We call this the \"rightmost Z-box.\"\n\nWhen processing position i, there are two cases:\n\n**Case 1: i > R (outside the current Z-box)**\n\nWe have no useful information about position i. Compute Z[i] from scratch by comparing characters starting at S[i] against the prefix S[0]. If Z[i] > 0, update [L, R] to [i, i + Z[i] - 1].\n\n**Case 2: i <= R (inside the current Z-box)**\n\nThis is where the optimization happens. Since S[L..R] matches S[0..R-L], we know that S[i..R] matches S[i-L..R-L]. Let k = i - L. Then S[i..R] is identical to S[k..R-L]. We already computed Z[k], so we can use it as a starting point:\n\n- If Z[k] < R - i + 1, then Z[i] = Z[k]. The match at position k ended before the boundary of the Z-box, so the match at position i will end at exactly the same relative position.\n- If Z[k] >= R - i + 1, then Z[i] is at least R - i + 1, but it might extend beyond R. We need to compare characters starting at R + 1 against the prefix starting at R - i + 1, and then update [L, R].\n\n**Interview Insight:** The Z-box optimization is a classic example of amortized analysis. Each character comparison either falls inside the current Z-box (and is resolved in O(1) using a previously computed value) or extends R to the right (which can happen at most n times total). This two-case structure is the reason the algorithm runs in O(n).\n\n---\n\n## Building the Z-Array: Step-by-Step\n\nLet us trace through the algorithm on a longer string to see the Z-box in action, and then look at the full implementation.\n\n**Trace: S = \"aabxaabxaab\"**\n\n\n```shell\nIndex: 0 1 2 3 4 5 6 7 8 9 10\nString: a a b x a a b x a a b\n```\n\n\n\n```shell\nInitial: L = 0, R = 0\n\ni = 1: i > R (1 > 0), compute from scratch\n S[1] = 'a' == S[0] = 'a', match\n S[2] = 'b' != S[1] = 'a', stop\n Z[1] = 1, update L = 1, R = 1\n\ni = 2: i > R (2 > 1), compute from scratch\n S[2] = 'b' != S[0] = 'a', stop\n Z[2] = 0\n\ni = 3: i > R (3 > 1), compute from scratch\n S[3] = 'x' != S[0] = 'a', stop\n Z[3] = 0\n\ni = 4: i > R (4 > 1), compute from scratch\n S[4..10] = \"aabxaab\" vs S[0..6] = \"aabxaab\"\n All 7 characters match, but we reach end of string\n Z[4] = 7, update L = 4, R = 10\n\ni = 5: i <= R (5 <= 10), use Z-box\n k = i - L = 5 - 4 = 1, Z[k] = Z[1] = 1\n R - i + 1 = 10 - 5 + 1 = 6\n Z[1] = 1 < 6, so Z[5] = 1 (copied directly)\n\ni = 6: i <= R (6 <= 10), use Z-box\n k = 6 - 4 = 2, Z[k] = Z[2] = 0\n Z[2] = 0 < 5, so Z[6] = 0 (copied directly)\n\ni = 7: i <= R (7 <= 10), use Z-box\n k = 7 - 4 = 3, Z[k] = Z[3] = 0\n Z[3] = 0 < 4, so Z[7] = 0 (copied directly)\n\ni = 8: i <= R (8 <= 10), use Z-box\n k = 8 - 4 = 4, Z[k] = Z[4] = 7\n R - i + 1 = 10 - 8 + 1 = 3\n Z[4] = 7 >= 3, so Z[8] >= 3, need to extend beyond R\n Compare S[11] vs S[3]: out of bounds, stop\n Z[8] = 3, update L = 8, R = 10\n\ni = 9: i <= R (9 <= 10), use Z-box\n k = 9 - 8 = 1, Z[k] = Z[1] = 1\n R - i + 1 = 10 - 9 + 1 = 2\n Z[1] = 1 < 2, so Z[9] = 1 (copied directly)\n\ni = 10: i <= R (10 <= 10), use Z-box\n k = 10 - 8 = 2, Z[k] = Z[2] = 0\n Z[2] = 0 < 1, so Z[10] = 0 (copied directly)\n\nFinal Z-array: [-, 1, 0, 0, 7, 1, 0, 0, 3, 1, 0]\n```\n\n\nNotice how at i = 5, 6, 7, 9, and 10, we did not compare a single character. We simply copied the answer from a previously computed position. The Z-box saved us significant work.\n\n\n```mermaid\nflowchart TD\n subgraph Trace[\"Z-Box Movement During Construction\"]\n direction TB\n T1[\"i=4: Compute from scratch
Z[4]=7, L=4, R=10\"]:::cyan\n T2[\"i=5: Inside Z-box, copy Z[1]=1
Z[5]=1\"]:::teal\n T3[\"i=6,7: Inside Z-box, copy 0
Z[6]=0, Z[7]=0\"]:::teal\n T4[\"i=8: Inside Z-box, Z[4]=7 >= 3
Extend beyond R, Z[8]=3\"]:::orange\n T5[\"i=9,10: Inside Z-box, copy
Z[9]=1, Z[10]=0\"]:::teal\n end\n\n T1 --> T2 --> T3 --> T4 --> T5\n\n classDef cyan fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n### Implementation\n\nHere is the complete Z-array construction in all six languages.\n\n### Java\n\n\n```java\npublic static int[] buildZArray(String s) {\n int n = s.length();\n int[] z = new int[n];\n int l = 0, r = 0;\n\n for (int i = 1; i < n; i++) {\n if (i < r) {\n z[i] = Math.min(r - i, z[i - l]);\n }\n while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {\n z[i]++;\n }\n if (i + z[i] > r) {\n l = i;\n r = i + z[i];\n }\n }\n\n return z;\n}\n```\n\n\n### Python\n\n\n```python\ndef build_z_array(s: str) -> list[int]:\n n = len(s)\n z = [0] * n\n l, r = 0, 0\n\n for i in range(1, n):\n if i < r:\n z[i] = min(r - i, z[i - l])\n while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n z[i] += 1\n if i + z[i] > r:\n l, r = i, i + z[i]\n\n return z\n```\n\n\n### C++\n\n\n```cpp\nvector buildZArray(const string& s) {\n int n = s.size();\n vector z(n, 0);\n int l = 0, r = 0;\n\n for (int i = 1; i < n; i++) {\n if (i < r) {\n z[i] = min(r - i, z[i - l]);\n }\n while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {\n z[i]++;\n }\n if (i + z[i] > r) {\n l = i;\n r = i + z[i];\n }\n }\n\n return z;\n}\n```\n\n\n### C#\n\n\n```csharp\npublic static int[] BuildZArray(string s) {\n int n = s.Length;\n int[] z = new int[n];\n int l = 0, r = 0;\n\n for (int i = 1; i < n; i++) {\n if (i < r) {\n z[i] = Math.Min(r - i, z[i - l]);\n }\n while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {\n z[i]++;\n }\n if (i + z[i] > r) {\n l = i;\n r = i + z[i];\n }\n }\n\n return z;\n}\n```\n\n\n### JavaScript\n\n\n```javascript\nfunction buildZArray(s) {\n const n = s.length;\n const z = new Array(n).fill(0);\n let l = 0, r = 0;\n\n for (let i = 1; i < n; i++) {\n if (i < r) {\n z[i] = Math.min(r - i, z[i - l]);\n }\n while (i + z[i] < n && s[z[i]] === s[i + z[i]]) {\n z[i]++;\n }\n if (i + z[i] > r) {\n l = i;\n r = i + z[i];\n }\n }\n\n return z;\n}\n```\n\n\n### TypeScript\n\n\n```typescript\nfunction buildZArray(s: string): number[] {\n const n = s.length;\n const z: number[] = new Array(n).fill(0);\n let l = 0, r = 0;\n\n for (let i = 1; i < n; i++) {\n if (i < r) {\n z[i] = Math.min(r - i, z[i - l]);\n }\n while (i + z[i] < n && s[z[i]] === s[i + z[i]]) {\n z[i]++;\n }\n if (i + z[i] > r) {\n l = i;\n r = i + z[i];\n }\n }\n\n return z;\n}\n```\n\n\nThe implementation is remarkably compact. The key line is `z[i] = Math.min(r - i, z[i - l])`, which initializes Z[i] using the Z-box before the while loop attempts any extension. If i is outside the Z-box (i >= r), this line is skipped and z[i] stays at 0, so the while loop computes everything from scratch.\n\n---\n\n## Pattern Matching with Z-Algorithm\n\nNow for the payoff. How do we use the Z-array to find all occurrences of a pattern P in a text T?\n\nThe trick is elegant: concatenate the pattern, a special separator character, and the text into a single string, then compute its Z-array.\n\n\n```shell\nS = P + \"$\" + T\n```\n\n\nThe separator \"$\" must be a character that does not appear in either P or T. This prevents any match from crossing the boundary between P and T.\n\nAfter computing the Z-array of S, any position i where Z[i] equals len(P) indicates that the substring starting at position i matches the entire pattern. Since positions 0 through len(P) - 1 belong to P, and position len(P) is the separator, the text positions start at len(P) + 1. A match at position i in S corresponds to a match at position i - len(P) - 1 in T.\n\n**Example: P = \"aab\", T = \"aabxaab\"**\n\n\n```shell\nS = \"aab$aabxaab\"\n\nIndex: 0 1 2 3 4 5 6 7 8 9 10\nString: a a b $ a a b x a a b\nZ-array: - 1 0 0 3 1 0 0 3 1 0\n ^ ^\n Z[4]=3=m Z[8]=3=m\n```\n\n\nZ[4] = 3 = len(P), so there is a match at position 4 - 3 - 1 = 0 in T. Z[8] = 3 = len(P), so there is a match at position 8 - 3 - 1 = 4 in T.\n\nThese are exactly the two positions where \"aab\" appears in \"aabxaab\".\n\n\n```mermaid\nflowchart LR\n subgraph Concat[\"Concatenated String S\"]\n direction LR\n P0[\"a\"]:::cyan\n P1[\"a\"]:::cyan\n P2[\"b\"]:::cyan\n SEP[\"$\"]:::teal\n T0[\"a\"]:::orange\n T1[\"a\"]:::orange\n T2[\"b\"]:::orange\n T3[\"x\"]:::orange\n T4[\"a\"]:::orange\n T5[\"a\"]:::orange\n T6[\"b\"]:::orange\n end\n\n M1[\"Z[4]=3=m
Match at T[0]\"]:::green\n M2[\"Z[8]=3=m
Match at T[4]\"]:::green\n\n T0 -.-> M1\n T4 -.-> M2\n\n classDef cyan fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n**Interview Insight:** The separator character is not just a convenience, it is essential for correctness. Without it, Z[i] could exceed len(P) if the text happens to continue matching beyond the pattern boundary. The separator guarantees that Z[i] never exceeds len(P) for positions in the text portion of the concatenated string, making the equality check Z[i] == m both necessary and sufficient.\n\n### Implementation\n\n### Java\n\n\n```java\npublic static List zSearch(String text, String pattern) {\n String concat = pattern + \"$\" + text;\n int[] z = buildZArray(concat);\n int m = pattern.length();\n List result = new ArrayList<>();\n\n for (int i = m + 1; i < concat.length(); i++) {\n if (z[i] == m) {\n result.add(i - m - 1);\n }\n }\n\n return result;\n}\n```\n\n\n### Python\n\n\n```python\ndef z_search(text: str, pattern: str) -> list[int]:\n concat = pattern + \"$\" + text\n z = build_z_array(concat)\n m = len(pattern)\n result = []\n\n for i in range(m + 1, len(concat)):\n if z[i] == m:\n result.append(i - m - 1)\n\n return result\n```\n\n\n### C++\n\n\n```cpp\nvector zSearch(const string& text, const string& pattern) {\n string concat = pattern + \"$\" + text;\n vector z = buildZArray(concat);\n int m = pattern.size();\n vector result;\n\n for (int i = m + 1; i < (int)concat.size(); i++) {\n if (z[i] == m) {\n result.push_back(i - m - 1);\n }\n }\n\n return result;\n}\n```\n\n\n### C#\n\n\n```csharp\npublic static List ZSearch(string text, string pattern) {\n string concat = pattern + \"$\" + text;\n int[] z = BuildZArray(concat);\n int m = pattern.Length;\n var result = new List();\n\n for (int i = m + 1; i < concat.Length; i++) {\n if (z[i] == m) {\n result.Add(i - m - 1);\n }\n }\n\n return result;\n}\n```\n\n\n### JavaScript\n\n\n```javascript\nfunction zSearch(text, pattern) {\n const concat = pattern + \"$\" + text;\n const z = buildZArray(concat);\n const m = pattern.length;\n const result = [];\n\n for (let i = m + 1; i < concat.length; i++) {\n if (z[i] === m) {\n result.push(i - m - 1);\n }\n }\n\n return result;\n}\n```\n\n\n### TypeScript\n\n\n```typescript\nfunction zSearch(text: string, pattern: string): number[] {\n const concat = pattern + \"$\" + text;\n const z: number[] = buildZArray(concat);\n const m = pattern.length;\n const result: number[] = [];\n\n for (let i = m + 1; i < concat.length; i++) {\n if (z[i] === m) {\n result.push(i - m - 1);\n }\n }\n\n return result;\n}\n```\n\n\n---\n\n## Why It Is O(n + m)\n\nThe Z-Algorithm's linear time complexity is not immediately obvious from the code, since there is a while loop nested inside a for loop. Let us understand why it is still O(n + m).\n\nThe key observation is that the pointer R only moves to the right. It never moves left. Every time the while loop executes an iteration and finds a matching character, R advances by one position (either because we are computing from scratch outside the Z-box, or because we are extending beyond R in the case where Z[k] >= R - i + 1).\n\nSince R starts at 0 and can advance at most to n (the length of the string), the total number of character comparisons made by all while loop iterations combined is at most n. Each iteration of the for loop that does not enter the while loop takes O(1) time (it just copies a value from a previously computed Z entry).\n\nSo the total work is:\n\n- **O(n) for the for loop iterations** (n-1 iterations, each O(1) excluding the while loop)\n- **O(n) for all while loop iterations combined** (R advances at most n times total)\n- **Total: O(n)**\n\nFor pattern matching with the concatenated string of length n + m + 1, the total time is O(n + m).\n\nThis is the same amortized argument that makes KMP linear. The difference is that KMP tracks how far we have matched into the pattern (variable j that never backtracks more than it advances), while the Z-Algorithm tracks the rightmost reached position R.\n\n---\n\n## Applications Beyond Pattern Matching\n\nThe Z-array is a versatile tool that extends well beyond simple string search. Here are some important applications.\n\n### String Compression / Smallest Period\n\nA string S has a period of length p if S can be formed by repeating a substring of length p (possibly with a partial repetition at the end). For example, \"abcabcab\" has period 3 because it is the string \"abc\" repeated 2.67 times.\n\nTo find the smallest period using the Z-array, look for the smallest index i (starting from 1) where i + Z[i] == n. If additionally n % i == 0, then S is a perfect repetition of S[0..i-1]. Even without the divisibility condition, i is the smallest period.\n\n\n```shell\nS = \"abcabcabc\"\nZ = [-, 0, 0, 6, 0, 0, 3, 0, 0]\n\ni = 3: i + Z[i] = 3 + 6 = 9 = n, and 9 % 3 == 0\nSmallest period = 3, string = \"abc\" repeated 3 times\n```\n\n\n### Sum of Scores of Built Strings (LeetCode 2223)\n\nThis problem asks: given a string S, for each position i, compute the length of the longest common prefix between S and S[i..n-1], then sum all those values. The answer is simply Z[1] + Z[2] + ... + Z[n-1] + n (adding n for Z[0] which represents the full string matching itself). The Z-array gives us the answer directly.\n\n### Pattern Occurrence Counting\n\nInstead of collecting all match positions, sometimes we just need the count. After building the Z-array of P + \"$\" + T, the count is the number of positions i (where i > len(P)) with Z[i] == len(P). This runs in O(n + m) time and uses O(n + m) space.\n\n**Interview Insight:** The Z-Algorithm is less commonly asked in interviews than KMP, but it often leads to cleaner and shorter solutions. If you are in an interview and asked to solve a string matching problem, Z-Algorithm is a perfectly valid choice. Its implementation is shorter than KMP, and explaining the Z-box concept is arguably more intuitive than explaining the failure function.\n\n---\n\n## Comparison with KMP\n\nBoth KMP and the Z-Algorithm achieve O(n + m) time for pattern matching, but they differ in important ways. Here is a side-by-side comparison:\n\n\n| Aspect | KMP | Z-Algorithm |\n|--------|-----|-------------|\n| **Core Data Structure** | Failure function (prefix function) | Z-array |\n| **What It Computes** | Length of longest proper prefix that is also a suffix | Length of longest prefix match at each position |\n| **Processing Direction** | Processes text left to right, one character at a time | Requires the full concatenated string upfront |\n| **Online/Streaming** | Yes. Can process text as a stream without knowing its length | No. Needs the full string to build Z-array |\n| **Space** | O(m) for the failure function, O(1) additional for the text scan | O(n + m) for the Z-array of the concatenated string |\n| **Ease of Implementation** | Moderate. The failure function construction has subtle edge cases | Simple. Short, symmetric code with fewer edge cases |\n| **Additional Applications** | Automaton construction, multiple pattern matching (Aho-Corasick extends KMP) | String periods, prefix matching queries, sum-of-scores problems |\n| **Code Length** | Typically 20-25 lines | Typically 15-20 lines |\n\n\nThe most important practical difference is the streaming capability. KMP can match patterns in a text stream where you receive one character at a time and need to report matches as they happen. The Z-Algorithm cannot do this because it needs the full text to compute the Z-array. If your problem involves streaming data, KMP is the better choice.\n\nOn the other hand, if you have the full text available and want the simplest possible implementation, the Z-Algorithm is hard to beat. The code is compact, the logic is clean, and the Z-array itself is useful for problems beyond pattern matching.\n\n**Interview Insight:** When an interviewer asks \"compare KMP and Z-Algorithm,\" the streaming distinction is the most important point to make. KMP processes text character by character and can report matches without seeing the rest of the text. Z-Algorithm needs to see everything first. This makes KMP suitable for real-time applications like network packet inspection, while Z-Algorithm is better for batch processing where the full input is available.\n\n---\n\n## Complexity Analysis\n\n### Time Complexity\n\n**Z-array construction: O(n)**\n\nAs discussed, the pointer R only moves right, and each character comparison either advances R or is resolved in O(1) using previously computed values. The total work across all iterations is bounded by 2n comparisons.\n\n**Pattern matching: O(n + m)**\n\nBuilding the concatenated string P + \"$\" + T takes O(n + m). Computing the Z-array of this string takes O(n + m). Scanning the Z-array for matches takes O(n + m). The overall time complexity is O(n + m).\n\n### Space Complexity\n\n**Z-array construction: O(n)**\n\nWe need the Z-array of length n and a few variables for L and R.\n\n**Pattern matching: O(n + m)**\n\nThe concatenated string has length n + m + 1, and the Z-array has the same length. Unlike KMP, which uses only O(m) space for the failure function and then processes the text in O(1) additional space, the Z-Algorithm requires O(n + m) space for the full Z-array of the concatenated string.\n\n\n| Operation | Time | Space |\n|-----------|------|-------|\n| Build Z-array of string of length n | O(n) | O(n) |\n| Pattern matching (pattern m, text n) | O(n + m) | O(n + m) |\n| Find smallest period | O(n) | O(n) |\n| Count pattern occurrences | O(n + m) | O(n + m) |\n\n\n---\n\n## Interview Questions\n\n### Q1: Define the Z-array and compute it for S = \"abcababc\".\n\n**Answer:** Z[i] is the length of the longest substring starting at position i that is also a prefix of S. For S = \"abcababc\":\n\n\n```shell\nIndex: 0 1 2 3 4 5 6 7\nString: a b c a b a b c\nZ-array: - 0 0 2 0 3 0 0\n```\n\n\n- Z[1] = 0: \"bcababc\" does not start with \"a\"... actually \"b\" != \"a\".\n- Z[2] = 0: \"cababc\" does not start with \"a\".\n- Z[3] = 2: \"ababc\" matches \"ab\" (first 2 characters).\n- Z[4] = 0: \"babc\" does not start with \"a\".\n- Z[5] = 3: \"abc\" matches \"abc\" (first 3 characters).\n- Z[6] = 0: \"bc\" does not start with \"a\".\n- Z[7] = 0: \"c\" does not start with \"a\".\n\n### Q2: Explain the Z-box optimization. Why does it make the algorithm O(n)?\n\n**Answer:** The Z-box [L, R] tracks the rightmost interval where a prefix match was found. When processing position i inside this interval (i <= R), we know that S[i..R] is identical to S[i-L..R-L] because the entire Z-box matches a prefix. So we can copy Z[i-L] as a starting value for Z[i] instead of comparing from scratch.\n\nThe algorithm is O(n) because the right boundary R only moves forward. Every character comparison in the while loop either: (a) extends R to a new position (which can happen at most n times total since R goes from 0 to n), or (b) does not happen because we copied a previously computed value. This gives us at most n character comparisons across all iterations of the outer loop, plus O(1) work per iteration for the copying case, yielding O(n) total.\n\n### Q3: How does the Z-array solve pattern matching? Why is the separator character necessary?\n\n**Answer:** We concatenate P + \"$\" + T into a single string S, then compute its Z-array. Any position i in the text portion where Z[i] == len(P) indicates a full pattern match, because it means S[i..i+m-1] matches the first m characters of S, which are exactly P.\n\nThe separator \"$\" (a character not in P or T) is necessary to prevent matches from \"leaking\" across the boundary. Without it, if T starts with a suffix of P, the Z-value at the boundary could exceed len(P), counting a partial match of P continued by the start of T as a longer prefix match. The separator forces Z[i] <= len(P) for all positions in the text portion, making the equality check Z[i] == m both necessary and sufficient.\n\n### Q4: Compare the Z-Algorithm with KMP. When would you prefer each one?\n\n**Answer:** Both achieve O(n + m) for pattern matching, but they differ in key ways:\n\n- **Streaming:** KMP can process text one character at a time (online), while Z-Algorithm needs the full text upfront. For real-time or streaming applications, KMP is the only option.\n- **Space:** KMP uses O(m) for the failure function plus O(1) for the scan. Z-Algorithm uses O(n + m) for the concatenated Z-array.\n- **Simplicity:** Z-Algorithm has shorter, more symmetric code. The Z-box logic is arguably more intuitive than the failure function.\n- **Versatility:** The Z-array directly answers \"how much prefix matches here,\" which is useful for problems like period detection and prefix score sums. KMP's failure function encodes the same information but less directly.\n\nPrefer KMP when processing streams, when memory is tight (O(m) vs O(n+m)), or when building on Aho-Corasick for multi-pattern matching. Prefer Z-Algorithm when you have the full text, want simpler code, or need the Z-array for additional applications.\n\n### Q5: How can the Z-array detect the periodic structure of a string?\n\n**Answer:** A string S of length n has a period of length p if S is formed by repeating a substring of length p. To find the smallest period, scan the Z-array from i = 1 and find the smallest i where i + Z[i] == n. This means the suffix starting at position i matches the prefix for the rest of the string, which is exactly the condition for S[0..i-1] being a period. If additionally n % i == 0, then S is a perfect repetition (like \"abcabc\" with period 3). If n % i != 0, the last repetition is partial (like \"abcab\" with period 3).\n\nFor example, S = \"ababab\": Z = [-, 0, 4, 0, 2, 0]. At i = 2, we have i + Z[i] = 2 + 4 = 6 = n and 6 % 2 == 0, so the smallest period is 2 and the string is \"ab\" repeated 3 times.\n\n---\n\n## Summary\n\nThe Z-Algorithm offers a clean, intuitive approach to linear-time string matching. By answering the simple question \"how much of the prefix do I see at each position?\", the Z-array captures the structural information needed for pattern matching and much more.\n\nThe core ideas to remember:\n\n- **Z[i]** is the length of the longest substring starting at position i that matches a prefix of the string.\n- The **Z-box [L, R]** tracks the rightmost interval where a prefix match extends, allowing us to reuse previously computed values instead of comparing characters redundantly.\n- The right boundary **R only moves forward**, giving us O(n) amortized time.\n- For pattern matching, **concatenate P + \"$\" + T** and look for positions where Z[i] == len(P).\n- Beyond matching, the Z-array finds **string periods**, answers **prefix match length queries**, and solves problems like LeetCode 2223.\n\n### String Matching Algorithms: The Complete Picture\n\nOver these five chapters, we have built up a toolkit of string matching algorithms, each with its own strengths:\n\n\n| Algorithm | Time | Space | Online? | Best For |\n|-----------|------|-------|---------|----------|\n| **Brute Force** | O(n*m) | O(1) | Yes | Short patterns, simple cases |\n| **KMP** | O(n+m) | O(m) | Yes | Streaming text, single pattern, when memory matters |\n| **Rabin-Karp** | O(n+m) avg | O(1) | Yes | Multiple pattern search, plagiarism detection |\n| **Z-Algorithm** | O(n+m) | O(n+m) | No | Clean implementation, period detection, prefix queries |\n\n\nBrute force gave us the baseline. KMP introduced the failure function to guarantee O(n + m) by never re-scanning matched characters. Rabin-Karp took a different approach with hashing, trading deterministic guarantees for simplicity and multi-pattern capability. And the Z-Algorithm showed that a direct, intuitive question about prefix matches leads to an elegant linear-time solution with applications beyond pattern matching.\n\nWith these four algorithms in your toolkit, you can handle any pattern matching problem an interviewer throws at you.\n\n---\n\n## References\n\n- Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. \"Introduction to Algorithms\" (CLRS), Chapter 32: String Matching\n- Gusfield, D. \"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology\", Cambridge University Press\n- [Z-function and its computation - CP-Algorithms](undefined)\n- [Sum of Scores of Built Strings - LeetCode 2223](undefined)\n- [String Matching in an Array - LeetCode 2845](undefined)","pageType":"dsa"}

Chapter 5: Z-Algorithm

Ashish Pratap Singh

Get Premium