The Z-algorithm
The Z-algorithm joins the pattern, a separator that appears in neither string, and the text into one string, and computes for every position how many characters from there match the very beginning. Any position whose value equals the pattern length is an occurrence. It keeps a window — the match starting furthest left that reaches furthest right — and inside that window copies an answer it already has instead of comparing again.
How far it jumps
Reuse the answer already known for the window you are inside.
When it is the right choice
It is the same linear guarantee Knuth-Morris-Pratt gives, from a different and arguably more transparent idea, and the z-array itself is useful well beyond matching: longest common prefixes, periodicity, and the borders that Knuth-Morris-Pratt’s own table records. The cost is the space — the array is as long as the text plus the pattern, where a prefix table is only as long as the pattern.
How it works
- Join the pattern, a separator that occurs in neither string, and the text.
- Walk along the joined string from the second character.
- If the position is inside the current window, copy the answer from the matching position near the start — but no further than the window reaches.
- From wherever the copy left off, compare character by character for as long as they agree.
- If this match reaches further right than the current window, it becomes the new window.
- Any position whose value equals the pattern length marks an occurrence in the text.
Worth noticing
- The copies counter and the comparisons counter together are the whole argument: almost every position is answered by copying, and the few that are not are what keeps the total linear.
- The separator matters. Without a character that appears in neither string, a value could run off the end of the pattern and into the text, and a false occurrence would be reported.
- The window only ever moves right. That is the invariant which makes the total number of comparisons linear rather than quadratic, and it is visible in the track as the run goes on.
Cost
- Best
- O(n + m)
- Average
- O(n + m)
- Worst
- O(n + m)
- Extra space
- O(n + m)
- Longest text
- 160 characters
- Longest pattern
- 24 characters
The limits are pedagogical rather than technical: one column is drawn per character, and a run has to stay short enough to sit and watch. A text and pattern that would take more than three thousand steps on this algorithm are refused before a single step is generated — and because that depends on the text itself and not only on its length, the tool counts the steps first rather than guessing from a formula.