strings.boyer_moore_search¶

The algorithm finds the pattern in given text using following rule.

The bad-character rule considers the mismatched character in Text. The next occurrence of that character to the left in Pattern is found,

If the mismatched character occurs to the left in Pattern, a shift is proposed that aligns text block and pattern.

If the mismatched character does not occur to the left in Pattern, a shift is proposed that moves the entirety of Pattern past the point of mismatch in the text.

If there is no mismatch then the pattern matches with text block.

Time ComplexityO(n/m)

n=length of main string m=length of pattern string

Classes¶

BoyerMooreSearch

Example usage:

Module Contents¶

class strings.boyer_moore_search.BoyerMooreSearch(text: str, pattern: str)¶

Example usage:

bms = BoyerMooreSearch(text=”ABAABA”, pattern=”AB”) positions = bms.bad_character_heuristic()

where ‘positions’ contain the locations where the pattern was matched.

bad_character_heuristic() → list[int]¶

Finds the positions of the pattern location.

>>> bms = BoyerMooreSearch(text="ABAABA", pattern="AB")
>>> bms.bad_character_heuristic()
[0, 3]
match_in_pattern(char: str) → int¶

Finds the index of char in pattern in reverse order.

Parameters :

char (chr): character to be searched

Returns :

i (int): index of char from last in pattern -1 (int): if char is not found in pattern

>>> bms = BoyerMooreSearch(text="ABAABA", pattern="AB")
>>> bms.match_in_pattern("B")
1
mismatch_in_text(current_pos: int) → int¶

Find the index of mis-matched character in text when compared with pattern from last.

Parameters :

current_pos (int): current index position of text

Returns :

i (int): index of mismatched char from last in text -1 (int): if there is no mismatch between pattern and text block

>>> bms = BoyerMooreSearch(text="ABAABA", pattern="AB")
>>> bms.mismatch_in_text(2)
3

thealgorithms-python

Navigation

index.md

  • Contributing guidelines
  • Getting Started
  • Community Channels
  • List of Algorithms
  • MIT License
  • API Reference
    • maths
    • other
    • sorts
    • graphs
    • hashes
    • matrix
    • ciphers
    • geodesy
    • physics
    • quantum
    • strings
    • fractals
    • geometry
    • graphics
    • knapsack
    • searches
    • financial
    • blockchain
    • scheduling
    • conversions
    • electronics
    • fuzzy_logic
    • backtracking
    • audio_filters
    • file_transfer
    • project_euler
    • greedy_methods
    • linear_algebra
    • neural_network
    • boolean_algebra
    • computer_vision
    • data_structures
    • networking_flow
    • web_programming
    • bit_manipulation
    • data_compression
    • machine_learning
    • cellular_automata
    • genetic_algorithm
    • divide_and_conquer
    • linear_programming
    • dynamic_programming
    • digital_image_processing

Related Topics

  • Documentation overview
    • API Reference
      • strings
        • Previous: strings.bitap_string_match
        • Next: strings.camel_case_to_snake_case
©2014, TheAlgorithms. | Powered by Sphinx 8.2.3 & Alabaster 1.0.0 | Page source