The **exact matching** problem is to find all occurrences of a
pattern string P of length n in a text string T of length m

Extreme examples:

- If P = ab and T = bba, there are no occurrences
- If P = aaa and T = aaaaa, there are three (overlapping) occurrences

The naive approach would attempt to find P at positions 1, 2, 3, ... m-n+1 in T, possibly using n comparisons at each position, resulting in a worst-case running time proportional to mn. This time can be improved by preprocessing the pattern (fundamental preprocessing) as follows:

Define Z_{i}(S) to be the length of the longest prefix of S that matches
a substring of S starting at position i.( i > 1 )

For example, Z_{4}(abbcabbdabc) = 0, Z_{5}(abbcabbdabc) = 3,
and Z_{9}(abbcabbdabc) = 2

Associated with each Z_{i}, define an interval [*l*_{i},
*r*_{i}]: (Z-box)

*r*_{i}is the furthest position reached by a match starting between 1 and i inclusive

i.e.*r*_{i}= max j + Z_{j}- 1, where 1 < j <= i*l*_{i}is some value of j where this max is attained

**Input **String S

**Output:** Array of Z_{i} values (*l*_{i},
*r*_{i} values can also be computed)

**Variables:** k (iteration number), *l* (*l*_{i}
value from previous iteration), *r* (*r*_{i} value from
previous iteration)

**Initial values:** k = 2, *l* = 0, *r* = 0

**Iteration k:**

Case I:If k >r, find Z_{k}explicitly. If this is positive, updaterto k+Z_{k}-1 andlto kIf k <=

r, let k' = k -l+ 1 be the position where S(k) matched whenrwas last updated

Case IIa:If Z_{k'}<r- k + 1, then Z_{k}= Z_{k'}andlandrare not changed

Case IIb:If Z_{k'}>=r- k + 1, compare characters starting atr+1 with characters starting atr-k+2 until a mismatch occurs at position q. Set Z_{k}= q - k,l= k,r= q-1