Usage: Perform string match using the Boyer-Moore algorithm. The text and pattern sizes are limited to 20 and 10, respectively. If the input is too large, it is truncated. Click the Next button to see a step in the algorithm. Click the Reset button to start over with a new text and a new pattern.

i: 1

↓

text

pattern

  1    i = m – 1; // m is the pattern size
  2    while i <= n – 1 // n is the text size
  3      Compare pattern with text[i – (m – 1) .. i] from right to left one by one.
  4      if they all match, done. 
  5      else
  6        let text[k] be the first one that does not match the corresponding
  7        character in pattern. Consider two cases:
  8        Case 1: If text[k] is not in the remaining pattern, slide the   
  9                pattern passing text[k]. Set i = k + m;
 10        Case 2: If text[k] is in pattern, find the last character, say
 11                pattern[j] in pattern that matches text[k] and slide the pattern
 12                right to align pattern[j] with text[k].
 13                Set i = k + m – j - 1.
 14    Finished with no match