StringsString Algorithms

Z-Algorithm

Compute for every position the length of the longest substring starting there that matches a prefix of the string, in linear time.

Learn Z-Algorithm →
a
a
0
b
1
c
2
a
3
b
4
y
5
$
6
a
7
b
8
x
9
a
10
b
11
c
12
a
13
b
14
c
15
a
16
b
17
y
18
z
0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1/38Concatenate pattern + '$' + text (the '$' separator never matches, so no z-value exceeds 6). z[i] = length of the longest substring starting at i that is also a prefix of s.
Current position iCharacters being extendedz[i] == |pattern|: matchCurrent Z-box [l, r]
PseudocodeLearn Z-Algorithm →
1s = pattern + "$" + text; z[0] = 0; l = r = 0
2for i in 1 .. len(s)-1:
3  if i <= r: z[i] = min(r - i + 1, z[i - l])   # reuse the Z-box
4  while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]: z[i] += 1
5  if i + z[i] - 1 > r: l = i; r = i + z[i] - 1
6  if z[i] == m: report match at i - m - 1
Variables
l0
r0
m6
Complexity
best O(n + m)
avg O(n + m)
worst O(n + m)
space O(n + m)
Speed