The Shift Table
The so-called match heuristic is used to compute the values
of this data structure. For every suffix of the pattern,
that eventually causes a
mismatch, the length of a safe shift is stored.
Suppose the scan of the pattern is done right to left and a
mismatch occurs at position j in the pattern.
pattern[j] differs from text[i+j-1].
If i+s is a starting position for the pattern in text
then, the following conditions hold:
-
cond1(j, s):
for each k s.t. j < k < (m+1), k
< (s+1) or
pat[k-s] = pat[k]
-
cond2(j, s):
if s < j then pat[j-s] differs from
pat[j]
D(j) = min{s > 0: cond1(j, s) and cond2(j, s) hold}
In the mismatch situation described above
i = i + D(j)
is a safe shift.
Back to the Applet