JavaScript: Implement Boyer-Moore string-search algorithm

JavaScript String: Exercise-51 with Solution

Boyer-Moore String Search

From Wikipedia,
In computer science, the Boyer–Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for practical string-search literature. It was developed by Robert S. Boyer and J Strother Moore in 1977. The original paper contained static tables for computing the pattern shifts without an explanation of how to produce them. The algorithm for producing the tables was published in a follow-on paper; this paper contained errors which were later corrected by Wojciech Rytter in 1980. The algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text). It is thus well-suited for applications in which the pattern is much shorter than the text or where it persists across multiple searches. The Boyer–Moore algorithm uses information gathered during the preprocess step to skip sections of the text, resulting in a lower constant factor than many other string search algorithms. In general, the algorithm runs faster as the pattern length increases. The key features of the algorithm are to match on the tail of the pattern rather than the head, and to skip along the text in jumps of multiple characters rather than searching every single character in the text.
Write a JavaScript function to implement the Boyer-Moore String Search Algorithm.
The Boyer–Moore string search algorithm allows linear time in search by skipping indices when searching inside a string for a pattern.
Test Data:
('THIS IS A TEST TEXT', 'TEST') -> 10
('THIS IS A TEST TEXT', 'TEST') -> 14

Sample Solution:

JavaScript Code:

/*
 * Source: shorturl.at/rvwPV
 * Implementation of the Boyer-Moore String Search Algorithm.
 * The Boyer–Moore string search algorithm allows linear time in
 * search by skipping indices when searching inside a string for a pattern.
 **/

// Function to build the Bad Match Table for Boyer-Moore algorithm
const buildBadMatchTable = (str) => {
  const tableObj = {} // Initialize an empty object to store bad match table
  const strLength = str.length // Length of the pattern
  // Loop through the pattern characters
  for (let i = 0; i < strLength - 1; i++) {
    // Store the distance from the end of the pattern for each character
    tableObj[str[i]] = strLength - 1 - i
  }
  // If the last character is not present in the table, add it with the full pattern length
  if (tableObj[str[strLength - 1]] === undefined) {
    tableObj[str[strLength - 1]] = strLength
  }
  return tableObj // Return the built bad match table
}

// Function to perform Boyer-Moore string search
const boyerMoore = (str, pattern) => {
  const badMatchTable = buildBadMatchTable(pattern) // Build the Bad Match Table for the pattern
  let offset = 0 // Initialize offset for string traversal
  const patternLastIndex = pattern.length - 1 // Index of the last character in the pattern
  const maxOffset = str.length - pattern.length // Maximum offset to avoid unnecessary comparisons

  // Iterate through the string until the maximum offset is reached
  while (offset <= maxOffset) {
    let scanIndex = 0 // Initialize index for pattern traversal
    // Compare characters of pattern with characters of string starting from current offset
    while (pattern[scanIndex] === str[scanIndex + offset]) {
      // If all characters of pattern match with substring of string starting from offset
      if (scanIndex === patternLastIndex) {
        // Return the starting index of pattern in the string
        return offset
      }
      scanIndex++ // Move to next character in pattern
    }
    const badMatchString = str[offset + patternLastIndex] // Character causing mismatch in string
    // If bad match character is present in the table, move offset accordingly
    if (badMatchTable[badMatchString]) {
      offset += badMatchTable[badMatchString]
    } else {
      offset++ // Move one position to the right in the string
    }
  }
  return -1 // Return -1 if pattern is not found in the string
}

// Test cases
console.log(boyerMoore('THIS IS A TEST TEXT', 'TEST')) // Output: 10 (index where 'TEST' starts)
console.log(boyerMoore('AAIOOOAADDZXYCAADAABAABA', 'AADA')) // Output: 9 (index where 'AADA' starts)

Output:

10
14

Flowchart:

Live Demo:

See the Pen javascript-string-exercise-51 by w3resource (@w3resource) on CodePen.

For more Practice: Solve these Related Problems:

• Write a JavaScript function that implements the Boyer-Moore algorithm to search for a pattern in a text and returns its index.
• Write a JavaScript function that preprocesses the pattern to create bad character and good suffix tables for efficient search.
• Write a JavaScript function that handles edge cases such as empty pattern or text and returns appropriate values.
• Write a JavaScript function that compares performance of Boyer-Moore with a simple string search for large inputs.

Improve this sample solution and post your code through Disqus.

Previous: Alphanumeric characters that are palindromes.
Next: Check exceeding word.