

_UpperCAmelCase		:       Any						    =	256
# Modulus to hash a string
_UpperCAmelCase		:       str						    =	100_0003





def  __lowerCamelCase     (			UpperCamelCase__       ,							UpperCamelCase__				):







							'''simple docstring'''






							snake_case_          =   len(UpperCamelCase__				)
							snake_case_          =   len(UpperCamelCase__				)
							if p_len > t_len:
														return False

							snake_case_          =   0
							snake_case_          =   0
							snake_case_          =   1

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





def  __lowerCamelCase     (			):







							'''simple docstring'''






							snake_case_          =   'abc1abc12'
							snake_case_          =   'alskfjaldsabc1abc1abc12k23adsfabcabc'
							snake_case_          =   'alskfjaldsk23adsfabcabc'
							assert rabin_karp(UpperCamelCase__       ,							UpperCamelCase__				) and not rabin_karp(UpperCamelCase__       ,							UpperCamelCase__				)

							# Test 2)
							snake_case_          =   'ABABX'
							snake_case_          =   'ABABZABABYABABX'
							assert rabin_karp(UpperCamelCase__       ,							UpperCamelCase__				)

							# Test 3)
							snake_case_          =   'AAAB'
							snake_case_          =   'ABAAAAAB'
							assert rabin_karp(UpperCamelCase__       ,							UpperCamelCase__				)

							# Test 4)
							snake_case_          =   'abcdabcy'
							snake_case_          =   'abcxabcdabxabcdabcdabcy'
							assert rabin_karp(UpperCamelCase__       ,							UpperCamelCase__				)

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


if __name__ == "__main__":
					test_rabin_karp()







from __future__ import annotations





def  __lowerCamelCase     (			UpperCamelCase__       ,							UpperCamelCase__ = None       ,							UpperCamelCase__ = None				):







							'''simple docstring'''






							if start is None:
														snake_case_          =   0

							if end is None:
														snake_case_          =   len(UpperCamelCase__				) - 1

							if start >= end:
														return

							snake_case_          =   (start + end) // 2

							slowsort(UpperCamelCase__       ,							UpperCamelCase__       ,							UpperCamelCase__				)
							slowsort(UpperCamelCase__       ,							mid + 1       ,							UpperCamelCase__				)

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

							slowsort(UpperCamelCase__       ,							UpperCamelCase__       ,							end - 1				)


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

					testmod()




