Search code examples
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').

    • Your text ends with 'xSS' and your pattern with 'USS'

    After shifting the pattern right 1:

    • Your text ends with 'SSy' (y unknown) and your pattern again with 'USS'

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

    If shifting right 6

    • Your text ends with 'USSabcde' (a-b unknown) and your pattern with 'USSENUSS'

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