Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

Search:

CA216      CA249      CA318

CA400      CA651      CA668


Boyer-Moore string search algorithm


Example

pattern = "STING"
string = "A STRING SEARCHING EXAMPLE CONSISTING OF TEXT"


  1. try to match first m characters
    STING
    A STRING SEARCHING EXAMPLE CONSISTING OF TEXT
    This fails. Slide pattern right to look for other matches.
    Note that R does not occur in pattern. So can slide it past R.
    You may be starting to guess that this method is for large alphabets (e.g. human text)
    while KMP is good for small alphabets (where one could rarely ever do this kind of sliding).

  2. STING
    A STRING SEARCHING EXAMPLE CONSISTING OF TEXT
    Fails again.
    Rightmost character S is in pattern precisely once, so slide until two S's line up.

  3. STING
    A STRING SEARCHING EXAMPLE CONSISTING OF TEXT
    No C in pattern. Slide past it.

  4. STING
    A STRING SEARCHING EXAMPLE CONSISTING OF TEXT
    No space in pattern. Slide past it.

  5. STING
    A STRING SEARCHING EXAMPLE CONSISTING OF TEXT
    No P in pattern. Slide past it.

  6. STING
    A STRING SEARCHING EXAMPLE CONSISTING OF TEXT
    No O in pattern. Slide past it.

  7. STING
    A STRING SEARCHING EXAMPLE CONSISTING OF TEXT
    Rightmost char T. Exactly one T in pattern. Slide to align them.

  8. STING
    A STRING SEARCHING EXAMPLE CONSISTING OF TEXT
    match


Skip table

For each character in alphabet found in the rightmost slot on a mismatch, this table tells you how many slots to shift the pattern right.

For all characters not in the pattern, table entry = m


For pattern STING:

S T I N G
4 3 2 1 5

If N is rightmost char on mismatch, shift right by 1 to line the N's up.


For pattern CONSISTING:

C O N S I S T I N G
9 8       4 3 2 1 10

Blank for a letter means the value for this letter is listed in the other copy.

There are two I's. Shift right by 2 not by 5, to avoid missing possible match.


For pattern DISGUSTING:

D I S G U S T I N G
9     6 5 4 3 2 1  

There are two G's.





Feeds      w2mind.org

On Internet since 1987.