


'''simple docstring'''




__snake_case    						=256
# Modulus to hash a string
__snake_case    						=1_000_003





def 	a_					( lowerCamelCase	:     str	, lowerCamelCase	:     str				):
   lowerCAmelCase     =			len(lowerCamelCase				)
   lowerCAmelCase     =			len(lowerCamelCase				)
   if p_len > t_len:
      return False

   lowerCAmelCase     =			0
   lowerCAmelCase     =			0
   lowerCAmelCase     =			1

   # Calculating the hash of pattern and substring of text
   for i in range(lowerCamelCase				):
      lowerCAmelCase     =			(ord(pattern[i]				) + p_hash * alphabet_size) % modulus
      lowerCAmelCase     =			(ord(text[i]				) + text_hash * alphabet_size) % modulus
      if i == p_len - 1:
         continue
      lowerCAmelCase     =			(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
      lowerCAmelCase     =			(
          (text_hash - ord(text[i]				) * modulus_power) * alphabet_size
          + ord(text[i + p_len]				)
      ) % modulus
   return False





def 	a_					( ):
   lowerCAmelCase     =			'abc1abc12'
   lowerCAmelCase     =			'alskfjaldsabc1abc1abc12k23adsfabcabc'
   lowerCAmelCase     =			'alskfjaldsk23adsfabcabc'
   assert rabin_karp(lowerCamelCase	, lowerCamelCase				) and not rabin_karp(lowerCamelCase	, lowerCamelCase				)

   # Test 2)
   lowerCAmelCase     =			'ABABX'
   lowerCAmelCase     =			'ABABZABABYABABX'
   assert rabin_karp(lowerCamelCase	, lowerCamelCase				)

   # Test 3)
   lowerCAmelCase     =			'AAAB'
   lowerCAmelCase     =			'ABAAAAAB'
   assert rabin_karp(lowerCamelCase	, lowerCamelCase				)

   # Test 4)
   lowerCAmelCase     =			'abcdabcy'
   lowerCAmelCase     =			'abcxabcdabxabcdabcdabcy'
   assert rabin_karp(lowerCamelCase	, lowerCamelCase				)

   # Test 5)
   lowerCAmelCase     =			'Lü'
   lowerCAmelCase     =			'Lüsai'
   assert rabin_karp(lowerCamelCase	, lowerCamelCase				)
   lowerCAmelCase     =			'Lue'
   assert not rabin_karp(lowerCamelCase	, lowerCamelCase				)
   print('Success.'				)


if __name__ == "__main__":
       test_rabin_karp()











from __future__ import annotations

lowerCamelCase__ :   Optional[int]					=							[-10, -5, 0, 5, 5.1, 11, 13, 21, 3, 4, -21, -10, -5, -1, 0]
lowerCamelCase__ :   List[Any]					=							[-5, 0, 5, 5.1, 11, 13, 21, -1, 4, -1, -10, -5, -1, 0, -1]

def 					UpperCAmelCase_							(      __UpperCAmelCase						:	list[float]							)					-> list[float]:
      SCREAMING_SNAKE_CASE_							=			[]
      SCREAMING_SNAKE_CASE_							=			len(__UpperCAmelCase							)

      for i in range(__UpperCAmelCase							):
            SCREAMING_SNAKE_CASE_							=			-1
            for j in range(i + 1			,			__UpperCAmelCase							):
                  if arr[i] < arr[j]:
                        SCREAMING_SNAKE_CASE_							=			arr[j]
                        break
            result.append(__UpperCAmelCase							)
      return result

def 					UpperCAmelCase_							(      __UpperCAmelCase						:	list[float]							)					-> list[float]:
      SCREAMING_SNAKE_CASE_							=			[]
      for i, outer in enumerate(__UpperCAmelCase							):
            SCREAMING_SNAKE_CASE_							=			-1
            for inner in arr[i + 1 :]:
                  if outer < inner:
                        SCREAMING_SNAKE_CASE_							=			inner
                        break
            result.append(__UpperCAmelCase							)
      return result

def 					UpperCAmelCase_							(      __UpperCAmelCase						:	list[float]							)					-> list[float]:
      SCREAMING_SNAKE_CASE_							=			len(__UpperCAmelCase							)
      SCREAMING_SNAKE_CASE_							=			[]
      SCREAMING_SNAKE_CASE_							=			[-1] * arr_size

      for index in reversed(range(__UpperCAmelCase							)							):
            if stack:
                  while stack[-1] <= arr[index]:
                        stack.pop()
                        if not stack:
                              break
            if stack:
                  SCREAMING_SNAKE_CASE_							=			stack[-1]
            stack.append(arr[index]							)
      return result


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

   testmod()
   print(next_greatest_element_slow(arr))
   print(next_greatest_element_fast(arr))
   print(next_greatest_element(arr))

   lowerCamelCase__ :   List[str]					=							(
       'from __main__ import arr, next_greatest_element_slow, '
       'next_greatest_element_fast, next_greatest_element'
   )
   print(
       'next_greatest_element_slow():',
       timeit('next_greatest_element_slow(arr)', setup=setup),
   )
   print(
       'next_greatest_element_fast():',
       timeit('next_greatest_element_fast(arr)', setup=setup),
   )
   print(
       '     next_greatest_element():',
       timeit('next_greatest_element(arr)', setup=setup),
   )