Z Function
Compute Z[i] = length of the longest substring starting at i that matches a prefix of s, in O(n). Search patterns via pat$txt.
Intuition
Maintain the rightmost match window [l, r] found so far (a segment known to equal a prefix). Inside it, position i mirrors position i−l of the prefix — copy Z[i−l] for free, capped at the window edge; only extend by direct comparison past r. Every comparison pushes r right, so total work is linear.
The Z-array gives, for each position, the length of the longest prefix match starting there — and it's built in linear time by reusing work. The [l, r] window is a previously-matched block: inside it, an earlier Z-value predicts the answer for free, so comparisons only ever extend past r. That reuse-what-you-matched idea is the same one behind KMP.
Approach
The Z-box [l, r]
s[l..r] equals s[0..r−l]. For i inside it, the answer is already partially known from the prefix's own Z values.
Copy, cap, extend
Z[i] = min(Z[i−l], r−i+1) as a starting point; then compare characters beyond r to extend. Update [l, r] if i's match reaches further right.
Pattern search
Build Z on pat + '$ + txt: any Z value equal to len(pat) marks a full occurrence.
Solution & live demo
Common pitfalls
Comparing from scratch at every position
for i in range(1, n):
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1if i <= r:
z[i] = min(r - i + 1, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1That's the O(n²) version — correct, but it re-derives matches already known. Inside the [l, r] window the text mirrors the prefix, so a previous Z-value gives a free starting length.
Omitting the r - i + 1 cap
z[i] = z[i - l]
z[i] = min(r - i + 1, z[i - l])
The mirrored value is only trustworthy as far as the window extends. Copying it wholesale asserts matches beyond r that were never verified, and the result is silently too large.
Starting the loop at index 0
for i in range(n):
for i in range(1, n):
z[0] would be the whole string matching itself, which is conventionally left as 0 and, worse, would set r to n - 1 immediately — making every later position think it sits inside a verified window.
Edge cases
Z = [-, n−1, n−2, …] — windows chain perfectly, still linear.
'$ must not appear in either string, guaranteeing no match spans it.