
'''simple docstring'''



UpperCamelCase__      :		List[str]       							=  256
# Modulus to hash a string
UpperCamelCase__      :		List[Any]       							=  1_000_003
def    lowerCAmelCase_	(				SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						)     ->     bool:




   """simple docstring"""
   _SCREAMING_SNAKE_CASE      =				len(SCREAMING_SNAKE_CASE_						)
   _SCREAMING_SNAKE_CASE      =				len(SCREAMING_SNAKE_CASE_						)
   if p_len > t_len:
      return False

   _SCREAMING_SNAKE_CASE      =				0
   _SCREAMING_SNAKE_CASE      =				0
   _SCREAMING_SNAKE_CASE      =				1

   # Calculating the hash of pattern and substring of text
   for i in range(SCREAMING_SNAKE_CASE_						):
      _SCREAMING_SNAKE_CASE      =				(ord(pattern[i]						) + p_hash * alphabet_size) % modulus
      _SCREAMING_SNAKE_CASE      =				(ord(text[i]						) + text_hash * alphabet_size) % modulus
      if i == p_len - 1:
         continue
      _SCREAMING_SNAKE_CASE      =				(modulus_power * alphabet_size) % modulus

   for i in range(0    ,      t_len - p_len + 1						):
      if text_hash == p_hash and text[i : i + p_len] == pattern:
         return True
      if i == t_len - p_len:
         continue
      # Calculate the https://en.wikipedia.org/wiki/Rolling_hash
      _SCREAMING_SNAKE_CASE      =				(
          (text_hash - ord(text[i]						) * modulus_power) * alphabet_size
          + ord(text[i + p_len]						)
      ) % modulus
   return False
def    lowerCAmelCase_	(				)     ->     None:




   """simple docstring"""
   _SCREAMING_SNAKE_CASE      =				"""abc1abc12"""
   _SCREAMING_SNAKE_CASE      =				"""alskfjaldsabc1abc1abc12k23adsfabcabc"""
   _SCREAMING_SNAKE_CASE      =				"""alskfjaldsk23adsfabcabc"""
   assert rabin_karp(SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						) and not rabin_karp(SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						)

   # Test 2)
   _SCREAMING_SNAKE_CASE      =				"""ABABX"""
   _SCREAMING_SNAKE_CASE      =				"""ABABZABABYABABX"""
   assert rabin_karp(SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						)

   # Test 3)
   _SCREAMING_SNAKE_CASE      =				"""AAAB"""
   _SCREAMING_SNAKE_CASE      =				"""ABAAAAAB"""
   assert rabin_karp(SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						)

   # Test 4)
   _SCREAMING_SNAKE_CASE      =				"""abcdabcy"""
   _SCREAMING_SNAKE_CASE      =				"""abcxabcdabxabcdabcdabcy"""
   assert rabin_karp(SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						)

   # Test 5)
   _SCREAMING_SNAKE_CASE      =				"""Lü"""
   _SCREAMING_SNAKE_CASE      =				"""Lüsai"""
   assert rabin_karp(SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						)
   _SCREAMING_SNAKE_CASE      =				"""Lue"""
   assert not rabin_karp(SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						)
   print("""Success."""						)


if __name__ == "__main__":
     test_rabin_karp()






'''simple docstring'''



UpperCamelCase__      :		Dict       							=  {
    "a": "AAAAA",
    "b": "AAAAB",
    "c": "AAABA",
    "d": "AAABB",
    "e": "AABAA",
    "f": "AABAB",
    "g": "AABBA",
    "h": "AABBB",
    "i": "ABAAA",
    "j": "BBBAA",
    "k": "ABAAB",
    "l": "ABABA",
    "m": "ABABB",
    "n": "ABBAA",
    "o": "ABBAB",
    "p": "ABBBA",
    "q": "ABBBB",
    "r": "BAAAA",
    "s": "BAAAB",
    "t": "BAABA",
    "u": "BAABB",
    "v": "BBBAB",
    "w": "BABAA",
    "x": "BABAB",
    "y": "BABBA",
    "z": "BABBB",
    " ": " ",
}


UpperCamelCase__      :		str       							=  {value: key for key, value in encode_dict.items()}
def    lowerCAmelCase_	(				SCREAMING_SNAKE_CASE_						)     ->     str:




   """simple docstring"""
   _SCREAMING_SNAKE_CASE      =				""""""
   for letter in word.lower():
      if letter.isalpha() or letter == " ":
         encoded += encode_dict[letter]
      else:
         raise Exception("""encode() accepts only letters of the alphabet and spaces"""						)
   return encoded
def    lowerCAmelCase_	(				SCREAMING_SNAKE_CASE_						)     ->     str:




   """simple docstring"""
   if set(SCREAMING_SNAKE_CASE_						) - {"A", "B", " "} != set():
      raise Exception("""decode() accepts only 'A', 'B' and spaces"""						)
   _SCREAMING_SNAKE_CASE      =				""""""
   for word in coded.split():
      while len(SCREAMING_SNAKE_CASE_						) != 0:
         decoded += decode_dict[word[:5]]
         _SCREAMING_SNAKE_CASE      =				word[5:]
      decoded += " "
   return decoded.strip()


if __name__ == "__main__":
     from doctest import testmod

     testmod()






