TheAlgorithms-Python

1
"""
2
The algorithm finds the pattern in given text using following rule.
3

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

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

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

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

16
Time Complexity : O(n/m)
17
    n=length of main string
18
    m=length of pattern string
19
"""
20

21
from __future__ import annotations
22

23

24
class BoyerMooreSearch:
25
    def __init__(self, text: str, pattern: str):
26
        self.text, self.pattern = text, pattern
27
        self.textLen, self.patLen = len(text), len(pattern)
28

29
    def match_in_pattern(self, char: str) -> int:
30
        """finds the index of char in pattern in reverse order
31

32
        Parameters :
33
            char (chr): character to be searched
34

35
        Returns :
36
            i (int): index of char from last in pattern
37
            -1 (int): if char is not found in pattern
38
        """
39

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

45
    def mismatch_in_text(self, current_pos: int) -> int:
46
        """
47
        find the index of mis-matched character in text when compared with pattern
48
        from last
49

50
        Parameters :
51
            current_pos (int): current index position of text
52

53
        Returns :
54
            i (int): index of mismatched char from last in text
55
            -1 (int): if there is no mismatch between pattern and text block
56
        """
57

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

63
    def bad_character_heuristic(self) -> list[int]:
64
        # searches pattern in text and returns index positions
65
        positions = []
66
        for i in range(self.textLen - self.patLen + 1):
67
            mismatch_index = self.mismatch_in_text(i)
68
            if mismatch_index == -1:
69
                positions.append(i)
70
            else:
71
                match_index = self.match_in_pattern(self.text[mismatch_index])
72
                i = (
73
                    mismatch_index - match_index
74
                )  # shifting index lgtm [py/multiple-definition]
75
        return positions
76

77

78
text = "ABAABA"
79
pattern = "AB"
80
bms = BoyerMooreSearch(text, pattern)
81
positions = bms.bad_character_heuristic()
82

83
if len(positions) == 0:
84
    print("No match found")
85
else:
86
    print("Pattern found in following positions: ")
87
    print(positions)
88