



"""simple docstring"""





import os
import string
import sys


lowerCamelCase  			=		1 << 8

lowerCamelCase  			=		{
    """tab""": ord("""\t"""),
    """newline""": ord("""\r"""),
    """esc""": 27,
    """up""": 65 + ARROW_KEY_FLAG,
    """down""": 66 + ARROW_KEY_FLAG,
    """right""": 67 + ARROW_KEY_FLAG,
    """left""": 68 + ARROW_KEY_FLAG,
    """mod_int""": 91,
    """undefined""": sys.maxsize,
    """interrupt""": 3,
    """insert""": 50,
    """delete""": 51,
    """pg_up""": 53,
    """pg_down""": 54,
}

lowerCamelCase  			=		KEYMAP["""up"""]
lowerCamelCase  			=		KEYMAP["""left"""]

if sys.platform == "win32":
  lowerCamelCase  			=		[]
  lowerCamelCase  			=		{
      B"""\xe0H""": KEYMAP["""up"""] - ARROW_KEY_FLAG,
      B"""\x00H""": KEYMAP["""up"""] - ARROW_KEY_FLAG,
      B"""\xe0P""": KEYMAP["""down"""] - ARROW_KEY_FLAG,
      B"""\x00P""": KEYMAP["""down"""] - ARROW_KEY_FLAG,
      B"""\xe0M""": KEYMAP["""right"""] - ARROW_KEY_FLAG,
      B"""\x00M""": KEYMAP["""right"""] - ARROW_KEY_FLAG,
      B"""\xe0K""": KEYMAP["""left"""] - ARROW_KEY_FLAG,
      B"""\x00K""": KEYMAP["""left"""] - ARROW_KEY_FLAG,
  }

for i in range(10):
  lowerCamelCase  			=		ord(str(i))
def   a__      ( ):
      if os.name == "nt":
            import msvcrt

            UpperCAmelCase_     					=				"mbcs"
            # Flush the keyboard buffer
            while msvcrt.kbhit():
                  msvcrt.getch()
            if len(lowerCAmelCase__ ) == 0:
                  # Read the keystroke
                  UpperCAmelCase_     					=				msvcrt.getch()

                  # If it is a prefix char, get second part
                  if ch in (b"\x00", b"\xe0"):
                        UpperCAmelCase_     					=				ch + msvcrt.getch()
                        # Translate actual Win chars to bullet char types
                        try:
                              UpperCAmelCase_     					=				chr(WIN_KEYMAP[cha] )
                              WIN_CH_BUFFER.append(chr(KEYMAP["mod_int"] ) )
                              WIN_CH_BUFFER.append(lowerCAmelCase__ )
                              if ord(lowerCAmelCase__ ) in (
                                  KEYMAP["insert"] - 1 << 9,
                                  KEYMAP["delete"] - 1 << 9,
                                  KEYMAP["pg_up"] - 1 << 9,
                                  KEYMAP["pg_down"] - 1 << 9,
                              ):
                                    WIN_CH_BUFFER.append(chr(126 ) )
                              UpperCAmelCase_     					=				chr(KEYMAP["esc"] )
                        except KeyError:
                              UpperCAmelCase_     					=				cha[1]
                  else:
                        UpperCAmelCase_     					=				ch.decode(lowerCAmelCase__ )
            else:
                  UpperCAmelCase_     					=				WIN_CH_BUFFER.pop(0 )
      elif os.name == "posix":
            import termios
            import tty

            UpperCAmelCase_     					=				sys.stdin.fileno()
            UpperCAmelCase_     					=				termios.tcgetattr(lowerCAmelCase__ )
            try:
                  tty.setraw(lowerCAmelCase__ )
                  UpperCAmelCase_     					=				sys.stdin.read(1 )
            finally:
                  termios.tcsetattr(lowerCAmelCase__      ,     termios.TCSADRAIN      ,     lowerCAmelCase__ )
      return ch


def   a__      ( ):
      UpperCAmelCase_     					=				get_raw_chars()
      if ord(lowerCAmelCase__ ) in [KEYMAP["interrupt"], KEYMAP["newline"]]:
            return char

      elif ord(lowerCAmelCase__ ) == KEYMAP["esc"]:
            UpperCAmelCase_     					=				get_raw_chars()
            if ord(lowerCAmelCase__ ) == KEYMAP["mod_int"]:
                  UpperCAmelCase_     					=				get_raw_chars()
                  if ord(lowerCAmelCase__ ) >= KEYMAP["arrow_begin"] - ARROW_KEY_FLAG and ord(lowerCAmelCase__ ) <= KEYMAP["arrow_end"] - ARROW_KEY_FLAG:
                        return chr(ord(lowerCAmelCase__ ) + ARROW_KEY_FLAG )
                  else:
                        return KEYMAP["undefined"]
            else:
                  return get_raw_chars()

      else:
            if char in string.printable:
                  return char
            else:
                  return KEYMAP["undefined"]









from __future__ import annotations






class     __a			:



	def __init__(    self				:     List[Any]					,						snake_case_				:     str					,						snake_case_				:     str)->				Optional[int]:
						__lowerCAmelCase ,						__lowerCAmelCase						 =text, pattern
						__lowerCAmelCase ,						__lowerCAmelCase						 =len(snake_case_), len(snake_case_)



	def 		UpperCamelCase				(    self				:     List[Any]					,						snake_case_				:     str)->				int:

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



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


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

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




