find T[1], we must discover a proper suffix of "A" which is also a prefix of pattern W. But there are no proper suffixes of "A", so we set T[1] = 0. To find T[2], we see that the substring W[0] - W[1] ("AB") has a proper suffix "B". However "B" is not a prefix of the pattern W. Therefore, we set T[2] = 0. Continuing to T[3], we first check the proper suffix of length 1, and as in the previous case it fails. Should we also check longer suffixes? No, we now note that there is a shortcut to checking all suffixes: let us say that we discovered a proper suffix which is a proper prefix (A proper prefix of a string is not equal to the string itself) and ending at W[2] with length 2 (the maximum possible); then its first character is also a proper prefix of W, hence a proper prefix itself, and it ends at W[1], which we already determined did not occur as T[2] = 0 and not T[2] = 1. Hence at each stage, the shortcut rule is that one needs to consider checking suffixes of a given size m+1 only if a valid suffix of size m was found at the previous stage (i.e. T[x] = m) and should not bother to check m+2, m+3, etc. Therefore, we need not even concern ourselves with substrings having length 2, and as in the previous case the sole one with length 1 fails, so T[3] = 0. We pass to the subsequent W[4], 'A'. The same logic shows that the longest substring we need to consider has length 1, and as in the previous case it fails since "D" is not a prefix of W. But instead of setting T[4] = 0, we can do better by noting that W[4] = W[0], and also that a look-up of T[4] implies the corresponding S character, S[m+4], was a mismatch and therefore S[m+4] ≠ 'A'. Thus there is no point in restarting the search at S[m+4]; we should begin at 1 position ahead. This means that we may shift pattern W by match length plus one character, so T[4] = -1. Considering now the next character, W[5], which is 'B': though by inspection the longest substring would appear to be 'A', we still set T[5] = 0. The reasoning is similar to why T[4] =