





'''simple docstring'''

from __future__ import annotations





def 		UpperCamelCase							(				_lowerCamelCase   :   str			):
    A__							=     len(lowerCAmelCase_			) // 2

    # choose the middle 3 elements
    A__							=     lst[m - 1 : m + 2]

    # if middle element is peak
    if three[1] > three[0] and three[1] > three[2]:
        return three[1]

    # if increasing, recurse on right
    elif three[0] < three[2]:
        if len(lst[:m]			) == 2:
            m -= 1
        return peak(lst[m:]			)

    # decreasing
    else:
        if len(lst[:m]			) == 2:
            m += 1
        return peak(lst[:m]			)


if __name__ == "__main__":
  import doctest

  doctest.testmod()







__a	 =      256
# Modulus to hash a string
__a	 =      100_0003
def 	_UpperCamelCase					(    lowerCAmelCase_	,    lowerCAmelCase_ )    ->bool:
   UpperCAmelCase      					=  len(lowerCAmelCase_ )
   UpperCAmelCase      					=  len(lowerCAmelCase_ )
   if p_len > t_len:
      return False

   UpperCAmelCase      					=  0
   UpperCAmelCase      					=  0
   UpperCAmelCase      					=  1

   # Calculating the hash of pattern and substring of text
   for i in range(lowerCAmelCase_ ):
      UpperCAmelCase      					=  (ord(pattern[i] ) + p_hash * alphabet_size) % modulus
      UpperCAmelCase      					=  (ord(text[i] ) + text_hash * alphabet_size) % modulus
      if i == p_len - 1:
         continue
      UpperCAmelCase      					=  (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
      UpperCAmelCase      					=  (
          (text_hash - ord(text[i] ) * modulus_power) * alphabet_size
          + ord(text[i + p_len] )
      ) % modulus
   return False
def 	_UpperCamelCase					(    )    ->None:
   UpperCAmelCase      					=  """abc1abc12"""
   UpperCAmelCase      					=  """alskfjaldsabc1abc1abc12k23adsfabcabc"""
   UpperCAmelCase      					=  """alskfjaldsk23adsfabcabc"""
   assert rabin_karp(lowerCAmelCase_	,    lowerCAmelCase_ ) and not rabin_karp(lowerCAmelCase_	,    lowerCAmelCase_ )

   # Test 2)
   UpperCAmelCase      					=  """ABABX"""
   UpperCAmelCase      					=  """ABABZABABYABABX"""
   assert rabin_karp(lowerCAmelCase_	,    lowerCAmelCase_ )

   # Test 3)
   UpperCAmelCase      					=  """AAAB"""
   UpperCAmelCase      					=  """ABAAAAAB"""
   assert rabin_karp(lowerCAmelCase_	,    lowerCAmelCase_ )

   # Test 4)
   UpperCAmelCase      					=  """abcdabcy"""
   UpperCAmelCase      					=  """abcxabcdabxabcdabcdabcy"""
   assert rabin_karp(lowerCAmelCase_	,    lowerCAmelCase_ )

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


if __name__ == "__main__":
 test_rabin_karp()



