Z Algorithm

Builds a Z-array where Z[i] is the length of the longest prefix of the string that also matches starting at position i, reusing overlap from a maintained [l, r) window. Concatenating pattern+'$'+text turns matching into scanning for Z[i] = pattern length.

Category: Strings
Time complexity: O(n + m)
Space complexity: O(n + m)

Pseudocode

s = pattern + "$" + text
maintain window [l, r) of known prefix match
reuse Z[i-l] when possible, extend by comparison
Z[i] = pattern length ⇒ match at i

Reference implementation

def z_array(s):
    l = r = 0
    for i in range(1, len(s)):
        if i &lt; r: z[i] = min(r - i, z[i - l])
        while s[z[i]] == s[i + z[i]]: z[i] += 1
        if i + z[i] &gt; r: l, r = i, i + z[i]

Open the interactive Z Algorithm visualisation →