Boyer-Moore string matching: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Compare right to left and combine bad-character and strong good-suffix shifts. This first-match version does not use the Galil rule.

Compare pattern characters from right to left. At a mismatch, compute both the bad-character displacement and the strong good-suffix displacement, then advance by their maximum.

Open the 3D visualization

Boyer-Moore string matching example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Boyer-Moore string matching

Finding the first exact occurrence of a fixed pattern in a longer text.

Choosing an alternative

Horspool uses a simpler single-character shift table. This view computes the full good-suffix table as well.

Worked example: input and state changes

Example input

ABAAABCDABC | ABC

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Text, aligned pattern, and good-suffix shifts before preprocessing.

    State at this checkpoint
    {
      "values": [
        "A",
        "B",
        "A",
        "A",
        "A",
        "B",
        "C",
        "D",
        "A",
        "B",
        "C",
        "A",
        "B",
        "C",
        "",
        "",
        "",
        "",
        "",
        "",
        "",
        "",
        0,
        0,
        0,
        0,
        "",
        "",
        "",
        "",
        "",
        "",
        ""
      ],
      "active": [],
      "kind": "matrix",
      "columns": 11,
      "goodSuffix": [
        3,
        3,
        3,
        1
      ],
      "result": -1
    }
  2. Step 2: Mismatch: bad-character shift 2, good-suffix shift 1; advance 2.

    State at this checkpoint
    {
      "values": [
        "A",
        "B",
        "A",
        "A",
        "A",
        "B",
        "C",
        "D",
        "A",
        "B",
        "C",
        "A",
        "B",
        "C",
        "",
        "",
        "",
        "",
        "",
        "",
        "",
        "",
        3,
        3,
        3,
        1,
        "",
        "",
        "",
        "",
        "",
        "",
        ""
      ],
      "active": [
        2,
        13
      ],
      "kind": "matrix",
      "columns": 11,
      "goodSuffix": [
        3,
        3,
        3,
        1
      ],
      "result": -1
    }
  3. Step 5: Shift the pattern.

    State at this checkpoint
    {
      "values": [
        "A",
        "B",
        "A",
        "A",
        "A",
        "B",
        "C",
        "D",
        "A",
        "B",
        "C",
        "",
        "",
        "",
        "",
        "A",
        "B",
        "C",
        "",
        "",
        "",
        "",
        3,
        3,
        3,
        1,
        "",
        "",
        "",
        "",
        "",
        "",
        ""
      ],
      "active": [],
      "kind": "matrix",
      "columns": 11,
      "goodSuffix": [
        3,
        3,
        3,
        1
      ],
      "result": -1
    }
  4. Step 7: Matching characters; compare from right to left.

    State at this checkpoint
    {
      "values": [
        "A",
        "B",
        "A",
        "A",
        "A",
        "B",
        "C",
        "D",
        "A",
        "B",
        "C",
        "",
        "",
        "",
        "",
        "A",
        "B",
        "C",
        "",
        "",
        "",
        "",
        3,
        3,
        3,
        1,
        "",
        "",
        "",
        "",
        "",
        "",
        ""
      ],
      "active": [
        5,
        16
      ],
      "kind": "matrix",
      "columns": 11,
      "goodSuffix": [
        3,
        3,
        3,
        1
      ],
      "result": -1
    }
  5. Step 9: First match starts at index 4.

    State at this checkpoint
    {
      "values": [
        "A",
        "B",
        "A",
        "A",
        "A",
        "B",
        "C",
        "D",
        "A",
        "B",
        "C",
        "",
        "",
        "",
        "",
        "A",
        "B",
        "C",
        "",
        "",
        "",
        "",
        3,
        3,
        3,
        1,
        "",
        "",
        "",
        "",
        "",
        "",
        ""
      ],
      "active": [],
      "kind": "matrix",
      "columns": 11,
      "goodSuffix": [
        3,
        3,
        3,
        1
      ],
      "result": 4
    }

Expected final state

First match starts at index 4.

Complexity and input bounds

Family: Strings. Time complexity: O(nm) worst case; O(n/m) best case.

Implementation detail: Three matrix rows show text, aligned pattern, and good-suffix shifts. UI inputs are bounded ASCII letters. Downloads use ASCII integer codes, allow an empty pattern, and return the first index or -1.

Space complexity: O(m + alphabet size) auxiliary storage, plus recorded frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

ASCII letters: text 1..32 | pattern 1..12. Case-sensitive.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

The strong good-suffix table has m+1 entries. Preprocessing must handle repeated borders. This first-match implementation does not include the Galil rule, so its stated worst-case bound is O(nm).

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// First occurrence or -1; empty pattern returns 0. n 0..32, m 0..12, text/pattern ASCII letter codes. Both bad-character and strong good-suffix preprocessing; no Galil rule. O(nm) worst case, O(m+256) auxiliary space. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(text, n, pattern, m) {
    if (m == 0) { return 0; }
    let last = Array(256).fill(0); let shift = Array(256).fill(0); let border = Array(256).fill(0); let i = m; let j = m + 1; let position = 0; let advance = 0;
    for (let c = 0; c < 256; c++) { last[c] = -1; }
    border[i] = j;
    while (i > 0) {
     while (j <= m && pattern[i-1] != pattern[j-1]) { if (shift[j] == 0) { shift[j] = j-i; } j = border[j]; }
     i--; j--; border[i] = j;
    }
    j = border[0];
    for (i = 0; i <= m; i++) { if (shift[i] == 0) { shift[i] = j; } if (i == j) { j = border[j]; } }
    for (i = 0; i < m; i++) { last[pattern[i]] = i; }
    while (position <= n-m) {
     j = m-1; while (j >= 0 && pattern[j] == text[position+j]) { j--; }
     if (j < 0) { return position; }
     advance = j-last[text[position+j]]; if (shift[j+1] > advance) { advance = shift[j+1]; } position += advance;
    }
    return -1;
}

Source

Primary research for the matching method. The playground uses bounded ASCII inputs and standalone teaching implementations rather than the original publication program.