|
| 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 | + |
| 22 | +classBoyerMooreSearch: |
| 23 | + |
| 24 | + |
| 25 | +def__init__(self,text,pattern): |
| 26 | +self.text,self.pattern=text,pattern |
| 27 | +self.textLen,self.patLen=len(text),len(pattern) |
| 28 | + |
| 29 | + |
| 30 | +defmatch_in_pattern(self,char): |
| 31 | +""" finds the index of char in pattern in reverse order |
| 32 | +
|
| 33 | + Paremeters : |
| 34 | + char (chr): character to be searched |
| 35 | +
|
| 36 | + Returns : |
| 37 | + i (int): index of char from last in pattern |
| 38 | + -1 (int): if char is not found in pattern |
| 39 | + """ |
| 40 | + |
| 41 | +foriinrange(self.patLen-1,-1,-1): |
| 42 | +ifchar==self.pattern[i]: |
| 43 | +returni |
| 44 | +return-1 |
| 45 | + |
| 46 | + |
| 47 | +defmismatch_in_text(self,currentPos): |
| 48 | +""" finds the index of mis-matched character in text when compared with pattern from last |
| 49 | +
|
| 50 | + Paremeters : |
| 51 | + currentPos (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 mis-match between pattern and text block |
| 56 | + """ |
| 57 | + |
| 58 | +foriinrange(self.patLen-1,-1,-1): |
| 59 | +ifself.pattern[i]!=self.text[currentPos+i]: |
| 60 | +returncurrentPos+i |
| 61 | +return-1 |
| 62 | + |
| 63 | + |
| 64 | +defbad_character_heuristic(self): |
| 65 | +# searches pattern in text and returns index positions |
| 66 | +positions= [] |
| 67 | +foriinrange(self.textLen-self.patLen+1): |
| 68 | +mismatch_index=self.mismatch_in_text(i) |
| 69 | +ifmismatch_index==-1: |
| 70 | +positions.append(i) |
| 71 | +else: |
| 72 | +match_index=self.match_in_pattern(self.text[mismatch_index]) |
| 73 | +i=mismatch_index-match_index#shifting index |
| 74 | +returnpositions |
| 75 | + |
| 76 | + |
| 77 | +text="ABAABA" |
| 78 | +pattern="AB" |
| 79 | +bms=BoyerMooreSearch(text,pattern) |
| 80 | +positions=bms.bad_character_heuristic() |
| 81 | + |
| 82 | +iflen(positions)==0: |
| 83 | +print("No match found") |
| 84 | +else: |
| 85 | +print("Pattern found in following positions: ") |
| 86 | +print(positions) |
| 87 | + |
| 88 | + |