The SBorder Table

For every prefix of the pattern, that eventually causes a mismatch, the length of a safe shift is stored.

If j denotes the length of the prefix of the pattern, then
sborder(j) = max{k |

  1. 0 < k < j and
  2. pattern[1 ... (k-1)] = pattern[(j-k+1) ... (j-1)] and
  3. pattern[k] differs from pattern[j]
}

Suppose the scan of the pattern is done left to right and a mismatch occurs at position j in the pattern.


pattern[j] differs from text[i+j-1].

In this situation

i := i + (j-sborder(j))
j := max(sborder(j), 1)
is a safe shift.

Back to the Applet