





'''simple docstring'''

class       UpperCAmelCase :  # Public class to implement a graph




  def __init__(self      :	Dict							,			A__      :	int							,			A__      :	int							,			A__      :	list[list[bool]]				)					-> Tuple:
      lowercase         = row
      lowercase         = col
      lowercase         = graph




  def 				UpperCAmelCase__   (self      :	Union[str, Any]							,			A__      :	int							,			A__      :	int							,			A__      :	list[list[bool]]				)					-> Optional[int]:
      return (
          0 <= i < self.ROW
          and 0 <= j < self.COL
          and not visited[i][j]
          and self.graph[i][j]
      )




  def 				UpperCAmelCase__   (self      :	List[str]							,			A__      :	int							,			A__      :	int							,			A__      :	list[list[bool]]				)					-> Dict:
      # Checking all 8 elements surrounding nth element
      lowercase         = [-1, -1, -1, 0, 0, 1, 1, 1]  # Coordinate order
      lowercase         = [-1, 0, 1, -1, 1, -1, 0, 1]
      lowercase         = True  # Make those cells visited
      for k in range(8				):
          if self.is_safe(i + row_nbr[k]							,			j + col_nbr[k]							,			UpperCamelCase_				):
              self.diffs(i + row_nbr[k]							,			j + col_nbr[k]							,			UpperCamelCase_				)





  def 				UpperCAmelCase__   (self      :	List[Any]				)					-> Optional[int]:  # And finally, count all islands.
      lowercase         = [[False for j in range(self.COL				)] for i in range(self.ROW				)]
      lowercase         = 0
      for i in range(self.ROW				):
          for j in range(self.COL				):
              if visited[i][j] is False and self.graph[i][j] == 1:
                  self.diffs(UpperCamelCase_							,			UpperCamelCase_							,			UpperCamelCase_				)
                  count += 1
      return count











'''simple docstring'''

from __future__ import annotations

class       UpperCAmelCase :




		def __init__(self      :	Dict							,			A__      :	str							,			A__      :	str				)					-> str:
						lowercase   ,							lowercase         = text, pattern
						lowercase   ,							lowercase         = len(A__				), len(A__				)




		def 				UpperCAmelCase__   (self      :	Any							,			A__      :	str				)					-> int:

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




		def 				UpperCAmelCase__   (self      :	List[Any]							,			A__      :	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 				UpperCAmelCase__   (self      :	Optional[Any]				)					-> list[int]:
						# searches pattern in text and returns index positions
						lowercase         = []
						for i in range(self.textLen - self.patLen + 1				):
										lowercase         = self.mismatch_in_text(A__				)
										if mismatch_index == -1:
														positions.append(A__				)
										else:
														lowercase         = self.match_in_pattern(self.text[mismatch_index]				)
														lowercase         = (
														    mismatch_index - match_index
														)  # shifting index lgtm [py/multiple-definition]
						return positions




__lowerCamelCase : List[str]											=			"ABAABA"
__lowerCamelCase : List[str]											=			"AB"
__lowerCamelCase : Union[str, Any]											=			BoyerMooreSearch(text, pattern)
__lowerCamelCase : List[str]											=			bms.bad_character_heuristic()

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




