Bad-Character Heuristic Analysis

In every case, we propose a shift of j-k. Negative values occur for case 3, but the other heuristic is always greater than 0, so the max guarantees progress.

Define $\lambda[a]$ to be the index of the right-most index of a in P. If $a \notin P$ then $\lambda[a] = 0$.

Then $j-\lambda[T[s+j]]$ is the bad-character shift we want. (j is current offset from s in T, T[s+j] is the current character.)