




"""simple docstring"""




lowerCAmelCase							:    List[Any]  							=     256
# Modulus to hash a string
lowerCAmelCase							:    Union[str, Any]  							=     100_0003



def 					a__				(       snake_case__ ,				snake_case__       )		->      int:
			lowerCamelCase       =      len(snake_case__       )
			lowerCamelCase       =      len(snake_case__       )
			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(snake_case__       ):
						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__				(       )		->      Optional[Any]:
			lowerCamelCase       =      '''abc1abc12'''
			lowerCamelCase       =      '''alskfjaldsabc1abc1abc12k23adsfabcabc'''
			lowerCamelCase       =      '''alskfjaldsk23adsfabcabc'''
			assert rabin_karp(snake_case__ ,				snake_case__       ) and not rabin_karp(snake_case__ ,				snake_case__       )

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

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

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

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


if __name__ == "__main__":
					test_rabin_karp()









"""simple docstring"""




from __future__ import annotations



def 					a__				(       snake_case__ ,				snake_case__ = None ,				snake_case__ = None       )		->      None:
			if start is None:
						lowerCamelCase       =      0

			if end is None:
						lowerCamelCase       =      len(snake_case__       ) - 1

			if start >= end:
						return

			lowerCamelCase       =      (start + end) // 2

			slowsort(snake_case__ ,				snake_case__ ,				snake_case__       )
			slowsort(snake_case__ ,				mid + 1 ,				snake_case__       )

			if sequence[end] < sequence[mid]:
						lowerCamelCase   ,     lowerCamelCase       =      sequence[mid], sequence[end]

			slowsort(snake_case__ ,				snake_case__ ,				end - 1       )


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

					testmod()



