the algorithm finds the pattern in given text using following rule the badcharacter 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 no mismatch then the pattern matches with text block time complexity onm nlength of main string mlength of pattern string 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 find the index of mismatched character in text when compared with pattern from last parameters currentpos 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 searches pattern in text and returns index positions 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 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 searches pattern in text and returns index positions shifting index lgtm py multiple definition
from __future__ import annotations


class BoyerMooreSearch:
    def __init__(self, text: str, pattern: str):
        self.text, self.pattern = text, pattern
        self.textLen, self.patLen = len(text), len(pattern)

    def match_in_pattern(self, char: str) -> int:
        

        for i in range(self.patLen - 1, -1, -1):
            if char == self.pattern[i]:
                return i
        return -1

    def mismatch_in_text(self, current_pos: int) -> int:
        

        for i in range(self.patLen - 1, -1, -1):
            if self.pattern[i] != self.text[current_pos + i]:
                return current_pos + i
        return -1

    def bad_character_heuristic(self) -> list[int]:
        
        positions = []
        for i in range(self.textLen - self.patLen + 1):
            mismatch_index = self.mismatch_in_text(i)
            if mismatch_index == -1:
                positions.append(i)
            else:
                match_index = self.match_in_pattern(self.text[mismatch_index])
                i = (
                    mismatch_index - match_index
                )  
        return positions


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

if len(positions) == 0:
    print("No match found")
else:
    print("Pattern found in following positions: ")
    print(positions)