Inside The Z Box
z[i] is the length of the longest common prefix of s and the suffix starting at i, with z[0] left as 0.
For s = "aabxaayaab":
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| s[i] | a | a | b | x | a | a | y | a | a | b |
| z[i] | 0 | 1 | 0 | 0 | ? | 1 | 0 | ? | 1 | 0 |
The algorithm keeps a window [l, r) for the rightmost prefix match found so far. An index inside that window starts at z[i] = min(r - i, z[i - l]); an index at or past r starts from zero. Either way the comparison loop then extends as far as it can. What are z[4] and z[7]?
Sign in to answer questions and track your progress
Sign In