3.8.4 · D5String Algorithms
Question bank — Z-algorithm — Z-array construction, O(n+m)
Quick symbol refresh so line one makes sense:
- is our string, length , positions numbered .
- = how many characters, starting at position , match the beginning (prefix) of .
- = the rightmost Z-box: the interval we already proved equals the prefix, chosen to have the largest possible right end .
- = the mirror of : the spot near the start of that is a photocopy of, when sits inside the box.
True or false — justify
The whole string is a prefix of itself, so should equal .
Technically true — the substring at matches the entire prefix of length . But we set by convention because using there would make the box logic and pattern-matching scan report a spurious "match" at index ; we simply never need that value.
If is , then .
True. Starting at we read , which matches the prefix for all 3 characters until the string ends, so .
Every entry of the Z-array satisfies .
True. The match starting at cannot use more characters than remain from to the end, and there are exactly of them.
Inside the box the equality is only probably true, so we should still verify it.
False. Inside the string provably equals the prefix, so is a proven fact, not a guess. Re-verifying it wastes the very work the algorithm was designed to skip.
If two positions and have the same mirror value , they must have the same -value.
False. The copy is only trusted while the mirror's match stays inside the box; if one of them reaches the boundary we must extend by comparison, giving a possibly larger answer.
The box can move backward (its can decrease) as grows.
False. We only update the box when a new match reaches further right than the current , so never decreases; jumps to the new starting index but the right end only marches forward.
Building the Z-array of a string of length never does more than about character comparisons in the while loop.
True. Each successful
while comparison pushes forward by one; goes from up to at most and never retreats, bounding all extensions to total.You can compute the Z-array from right to left instead of left to right and get the same complexity.
False in spirit — the whole method relies on already-known matches to the left (smaller indices) to fill the box, so processing left to right is essential; a right-to-left pass would have no reused information.
Spot the error
"For , set directly and move on."
The error is skipping the cap. If extends past the box edge , you'd claim matches beyond that were never checked; you must use and then let the
while verify anything past the edge."After computing , always set to keep the box fresh."
The error is unconditional updating. If this shrinks , destroying the " only increases" invariant and the amortized proof. Update only when the new match reaches further right.
"Case B where means the answer is exactly ."
The error is stopping at the boundary. Reaching the edge only guarantees the match up to ; beyond there may be more matching characters, so you must keep comparing from onward.
"To find pattern in text , just concatenate and look for ."
The error is the missing separator. Without a sentinel, a match could straddle the – boundary and count characters of as if they were text, giving false hits. Use with absent from both.
"The while loop condition can be just s[Z[i]] == s[i+Z[i]]."
The error is the missing bounds check. You must also require , otherwise you read past the end of the string and either crash or compare garbage.
" where — I'll use as the mirror instead."
The error is mirroring against the wrong endpoint. The box mirrors the prefix, whose left end aligns with , so the offset into the prefix is , not .
"Case A () needs special code separate from Case B."
Not an error in logic but in economy — Case A is just Case B with initialized to and no cap, so the single
while loop handles both; writing separate branches is redundant.Why questions
Why do we call the box the rightmost box and not just "a box"?
Because among all intervals known to match the prefix, we keep the one whose right end is largest — that maximizes how many future positions fall inside it and get answered for free.
Why does copying the mirror value give linear time rather than just being a nice shortcut?
Every position it answers for free costs zero comparisons, so all real character work is confined to the
while loop, and that loop is bounded by how far advances — at most steps overall.Why does the mismatch that ended the mirror's match "repeat" at in sub-case B1?
Because that mismatch happened at a position still inside the box, and inside the box is an exact copy of the prefix, so the identical mismatch must occur at the corresponding spot near .
Why is the naive method specifically on ?
Every starting index matches the prefix all the way to the end, so index does about comparisons, and summing those gives -ish work.
Why must the separator character be absent from both and , not just one?
If appeared in either string the algorithm could match it as an ordinary character, letting a "match" leak across the boundary and reporting positions that don't really contain the whole pattern.
Why does the min cap make the while do zero work in the pure B1 case?
When the cap leaves , and the next character to test lies at a position where the mirror already found a mismatch, so the very first
while comparison fails and no extension happens.Why can never be defined using positions to the right of in the prefix comparison?
By definition compares against , i.e. the prefix that always starts at position ; the comparison walks forward from both anchors, never referencing anything to the right of the prefix start.
Edge cases
What is for a string of length , say ?
Only exists and it is set to by convention; there are no other indices, and the algorithm's loop from to simply doesn't run.
What happens to the Z-array of a string where every character is distinct, e.g. ?
Every for is , because no position after starts with the prefix's first character ; no box is ever created.
If the pattern equals the whole text (), what does the pattern-matching build report?
In the position right after the separator has , so it reports exactly one match at text index — the pattern occupies the whole text once.
What is (the last position) at most, and when does it hit that max?
At most , since only one character remains; it equals exactly when the last character equals , and otherwise.
Can the box ever have ?
Yes. When a position matches the prefix for exactly one character () and reaches further right than before, the box becomes a single point , still a valid "matches the prefix for length 1" interval.
What if exactly (on the boundary, not strictly inside)?
It still counts as Case B (): the mirror gives a value, the cap is at most, and the
while verifies any extension past .Does an empty pattern make sense in the construction?
An empty pattern has , so would "match" everywhere, which correctly reflects that the empty string occurs at every position — usually guarded against as a trivial special case.
Related tools that trade blows with the Z-array on these same tasks: KMP failure function, String Hashing, Suffix Array, Suffix Automaton, Manacher's Algorithm, and the Amortized Analysis argument that underlies the linear bound.