The Last Table
The so-called occurrence heuristic is used to compute the values
of this data structure. For every character c of the text,
that eventually causes a
mismatch, the length of a safe shift is stored.
Let last(c) be the last position of an occurrence of character
c
in the pattern. If there is no occurrence, last(c) is set to zero.
If pattern[j] differs from text[i+j-1] then
i = i + max(1,
j-last(text[i+j-1]))
is a safe shift.
Back to the Applet