Z-function
z[i] is how many letters starting at position i match the start of the word. Computing each from scratch repeats work. Instead, remember the furthest match found so far, the box [l, r): inside it the word is a copy of its own start, so a position can borrow the answer of its twin near the start.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s | a | a | b | x | a | a | b | x | c | a | a | b |
| z | – |
For each position in "aabxaabxcaab", how many letters starting there match the start of the word?
1function zFunction(s) {2 const z = new Array(s.length).fill(0);3 for (let i = 1, l = 0, r = 0; i < s.length; i++) {4 if (i < r) z[i] = Math.min(r - i, z[i - l]);5 while (i + z[i] < s.length && s[z[i]] === s[i + z[i]]) z[i]++;6 if (i + z[i] > r) { l = i; r = i + z[i]; }7 }8 return z;9}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | every letter is compared a bounded number of times |
| average | n | any word |
| worst | n | where comparing each position from scratch takes n² |
| space | n | one value per position |
Where it breaks
- Searching for a pattern with it. Join pattern, a separator and text, then look for z values equal to the pattern's length. Pick Pattern search: the space acts as the separator, and positions with z = 3 mark each "aba" in the text.
- Trusting the box too far. A borrowed value is only certain up to the end of the box, which is why the code takes min(r − i, z[i − l]) and then keeps comparing past r.
- Repetitive words. Pick aaaaaaaa: from scratch, every position compares to the end, about n²/2 compares. With the box, each letter beyond r is compared once.