29.3 The restart vector

Function: %kmp-make-restart-vector item= item-ref pattern pattern-start pattern-past

Build a restart vector, to be used to search sequences for the occurrence of the selected subsequence of pattern.

The definition of the restart vector V for string P is: If we have matched elements 0 ... i-1 of P against some search sequence T:

P[i-1] = T[k]
P[i-2] = T[k-1]
...
P[0] = T[k-(i-1)]

and P[i] does not match T[k], then reset i := V[i], and try again to match T[k]. If V[i] = -1: move on to T[k+1] and P[0].