Z String Search

The Z-algorithm finds occurrences of a “word” $W$ within a main “text string” $T$ in linear time $O(|W| + |T|)$.

Given a string $S$ of length $n$, the algorithm produces an array, $Z$ where $Z[i]$ represents the longest substring starting from $S[i]$ which is also a prefix of $S$. Finding $Z$ for the string obtained by concatenating the word, $W$ with a nonce character, say $$$ followed by the text, $T$, helps with pattern matching, for if there is some index $i$ such that $Z[i]$ equals the pattern length, then the pattern must be present at that point.

While the $Z$ array can be computed with two nested loops in $O(|W| * |T|)$ time, the following strategy shows how to obtain it in linear time, based on the idea that as we iterate over the letters in the string (index $i$ from $1$ to $n - 1$), we maintain an interval $[L, R]$ which is the interval with maximum $R$ such that $1 ≤ L ≤ i ≤ R$ and $S[L…R]$ is a prefix that is also a substring (if no such interval exists, just let $L = R = - 1$). For $i = 1$, we can simply compute $L$ and $R$ by comparing $S[0…]$ to $S[1…]$.

Example of Z array

Index      0   1   2   3   4   5   6   7   8   9  10  11
Text       a   a   b   c   a   a   b   x   a   a   a   z
Z values   X   1   0   0   3   1   0   0   2   2   1   0

Other examples

str =  a a a a a a
Z[] =  x 5 4 3 2 1

str =  a a b a a c d
Z[] =  x 1 0 2 1 0 0

str =  a b a b a b a b
Z[] =  x 0 6 0 4 0 2 0

Example of Z box

z-box

Complexity

Time: $O( W + T )$
Space: $O( W )$

Implementations

1
# TODO: Implement in Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// let pattern = "aab";
// let text = "aabxaabxcaabxaabxay";
const pattern = 'abc';
const text = 'xabcabzabc';

const len = pattern.length + text.length + 1;

const z = new Array(len);
z[0] = 0;

function createZarr(concat) {
  let left;
  let right;
  let N;
  N = concat.length;
  left = 0;
  right = 0;
  for (let i = 1; i < N; i++) {
    
    if (i > right) {
      left = right = i;
      while (right < N && concat[right] === concat[right - left]) {
        
        right++;
      }
      
      z[i] = (right - left);
      
      console.log('--------------------------------');
      console.log(`Value of z[${i}] = the length of the substring starting from ${i} which is also the prefix of the concatinated string(=${right - left})`);
      console.log('--------------------------------');
      
      right--;
    } else if (z[i - left] < (right - i + 1)) {
      
      z[i] = z[i - left];
      
    } else {
      
      console.log(`The substring from index ${i - left} will cross the right end.`);
      
      left = i;
      while (right < N && concat[right] === concat[right - left]) {
        
        right++;
      }
      
      z[i] = (right - left);
      right--;
      
      console.log('--------------------------------');
      console.log(`Value of z[${i}] = the length of the substring starting from ${i} which is also the prefix of the concatinated string(=${right - left})`);
      console.log('--------------------------------');
      
    }
    
  }
}

const concat = `${pattern}$${text}`;

const patLen = pattern.length;
createZarr(concat);

console.log('The Values in Z array equal to the length of the pattern indicates the index at which the pattern is present');
console.log('===================================');
for (let i = 0; i < len; i++) {
  if (z[i] === patLen) {
    const pos = i - (patLen + 1);
    console.log(`Pattern Found at index ${pos}`);
  }
}
console.log('===================================');