algorithmstring-matchingboyer-moore

Boyer-Moore algorithm. Understanding good suffix shift example from course resource


Good suffix example from course resource.

SUSSENUSS

0 !S = 2

1 !SS = 6

2 !USS = 8

3 !NUSS = 5

8 for the rest of them.

My question is: Why is !SS = 6 and not = 1, as US after one step matches !SS ?


Solution

  • !SS means: 'SS' is a suffix, 'xSS' is not (x != 'U').

    After shifting the pattern right 1:

    There is no valid value for y that 'SSy' could match 'USS'

    If shifting right 6

    This may match if 'abcde' == 'ENUSS'