






"""simple docstring"""



import itertools
import string
from collections.abc import Generator, Iterable




def      _lowerCAmelCase		(							UpperCAmelCase__       :					Iterable[str],						UpperCAmelCase__       :					int      )		->Generator[tuple[str, ...], None, None]:
						A__						:  List[str]		  =  iter(UpperCAmelCase__      )
						while True:
												A__						:  int		  =  tuple(itertools.islice(UpperCAmelCase__,						UpperCAmelCase__      )      )
												if not chunk:
																		return
												yield chunk




def      _lowerCAmelCase		(							UpperCAmelCase__       :					str      )		->str:
						A__						:  Union[str, Any]		  =  """""".join([c.upper() for c in dirty if c in string.ascii_letters]      )
						A__						:  Optional[Any]		  =  """"""

						if len(UpperCAmelCase__      ) < 2:
												return dirty

						for i in range(len(UpperCAmelCase__      ) - 1      ):
												clean += dirty[i]

												if dirty[i] == dirty[i + 1]:
																		clean += "X"

						clean += dirty[-1]

						if len(UpperCAmelCase__      ) & 1:
												clean += "X"

						return clean




def      _lowerCAmelCase		(							UpperCAmelCase__       :					str      )		->list[str]:
						# I and J are used interchangeably to allow
						# us to use a 5x5 table (25 letters)
						A__						:  List[Any]		  =  """ABCDEFGHIKLMNOPQRSTUVWXYZ"""
						# we're using a list instead of a '2d' array because it makes the math
						# for setting up the table and doing the actual encoding/decoding simpler
						A__						:  Optional[Any]		  =  []

						# copy key chars into the table if they are in `alphabet` ignoring duplicates
						for char in key.upper():
												if char not in table and char in alphabet:
																		table.append(UpperCAmelCase__      )

    # fill the rest of the table in with the remaining alphabet chars
						for char in alphabet:
												if char not in table:
																		table.append(UpperCAmelCase__      )

						return table




def      _lowerCAmelCase		(							UpperCAmelCase__       :					str,						UpperCAmelCase__       :					str      )		->str:
						A__						:  Optional[int]		  =  generate_table(UpperCAmelCase__      )
						A__						:  str		  =  prepare_input(UpperCAmelCase__      )
						A__						:  Optional[Any]		  =  """"""

						# https://en.wikipedia.org/wiki/Playfair_cipher#Description
						for chara, chara in chunker(UpperCAmelCase__,						2      ):
												A__						:  Dict		  =  divmod(table.index(UpperCAmelCase__      ),						5      )
												A__						:  Union[str, Any]		  =  divmod(table.index(UpperCAmelCase__      ),						5      )

												if rowa == rowa:
																		ciphertext += table[rowa * 5 + (cola + 1) % 5]
																		ciphertext += table[rowa * 5 + (cola + 1) % 5]
												elif cola == cola:
																		ciphertext += table[((rowa + 1) % 5) * 5 + cola]
																		ciphertext += table[((rowa + 1) % 5) * 5 + cola]
												else:  # rectangle
																		ciphertext += table[rowa * 5 + cola]
																		ciphertext += table[rowa * 5 + cola]

						return ciphertext




def      _lowerCAmelCase		(							UpperCAmelCase__       :					str,						UpperCAmelCase__       :					str      )		->str:
						A__						:  Optional[Any]		  =  generate_table(UpperCAmelCase__      )
						A__						:  Any		  =  """"""

						# https://en.wikipedia.org/wiki/Playfair_cipher#Description
						for chara, chara in chunker(UpperCAmelCase__,						2      ):
												A__						:  List[Any]		  =  divmod(table.index(UpperCAmelCase__      ),						5      )
												A__						:  str		  =  divmod(table.index(UpperCAmelCase__      ),						5      )

												if rowa == rowa:
																		plaintext += table[rowa * 5 + (cola - 1) % 5]
																		plaintext += table[rowa * 5 + (cola - 1) % 5]
												elif cola == cola:
																		plaintext += table[((rowa - 1) % 5) * 5 + cola]
																		plaintext += table[((rowa - 1) % 5) * 5 + cola]
												else:  # rectangle
																		plaintext += table[rowa * 5 + cola]
																		plaintext += table[rowa * 5 + cola]

						return plaintext














"""simple docstring"""



from __future__ import annotations






class 							__SCREAMING_SNAKE_CASE						:


							def __init__(			self      :						Any			,    snake_case      :						str			,    snake_case      :						str							):
													'''simple docstring'''





													A__  ,  A__						:  List[str]		  =  text, pattern
													A__  ,  A__						:  List[str]		  =  len(snake_case							), len(snake_case							)


							def 						_UpperCamelCase       (			self      :						str			,    snake_case      :						str							):
													'''simple docstring'''





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


							def 						_UpperCamelCase       (			self      :						Any			,    snake_case      :						int							):
													'''simple docstring'''





													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      :						Union[str, Any]							):
													'''simple docstring'''





													A__						:  str		  =  []
													for i in range(self.textLen - self.patLen + 1							):
																			A__						:  List[Any]		  =  self.mismatch_in_text(snake_case							)
																			if mismatch_index == -1:
																									positions.append(snake_case							)
																			else:
																									A__						:  Dict		  =  self.match_in_pattern(self.text[mismatch_index]							)
																									A__						:  Union[str, Any]		  =  (
																									    mismatch_index - match_index
																									)  # shifting index lgtm [py/multiple-definition]
													return positions




A_    =							'''ABAABA'''
A_    =							'''AB'''
A_    =							BoyerMooreSearch(text, pattern)
A_    =							bms.bad_character_heuristic()

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






