




"""simple docstring"""







__A   :  List[str]					=      2_5_6
# Modulus to hash a string
__A   :  List[Any]					=      1_0_0_0_0_0_3

def 						snake_case__       (					_lowerCamelCase,  _lowerCamelCase				)			->bool:






		"""simple docstring"""


		__lowercase				:		Any												=				len(SCREAMING_SNAKE_CASE_				)
		__lowercase				:		Optional[int]												=				len(SCREAMING_SNAKE_CASE_				)
		if p_len > t_len:
				return False

		__lowercase				:		int												=				0
		__lowercase				:		Any												=				0
		__lowercase				:		Dict												=				1

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

def 						snake_case__       (					)			->None:






		"""simple docstring"""


		__lowercase				:		List[Any]												=				"abc1abc12"
		__lowercase				:		int												=				"alskfjaldsabc1abc1abc12k23adsfabcabc"
		__lowercase				:		Optional[Any]												=				"alskfjaldsk23adsfabcabc"
		assert rabin_karp(SCREAMING_SNAKE_CASE_,  SCREAMING_SNAKE_CASE_				) and not rabin_karp(SCREAMING_SNAKE_CASE_,  SCREAMING_SNAKE_CASE_				)

		# Test 2)
		__lowercase				:		str												=				"ABABX"
		__lowercase				:		List[str]												=				"ABABZABABYABABX"
		assert rabin_karp(SCREAMING_SNAKE_CASE_,  SCREAMING_SNAKE_CASE_				)

		# Test 3)
		__lowercase				:		Optional[int]												=				"AAAB"
		__lowercase				:		Optional[Any]												=				"ABAAAAAB"
		assert rabin_karp(SCREAMING_SNAKE_CASE_,  SCREAMING_SNAKE_CASE_				)

		# Test 4)
		__lowercase				:		Tuple												=				"abcdabcy"
		__lowercase				:		List[str]												=				"abcxabcdabxabcdabcdabcy"
		assert rabin_karp(SCREAMING_SNAKE_CASE_,  SCREAMING_SNAKE_CASE_				)

		# Test 5)
		__lowercase				:		str												=				"Lü"
		__lowercase				:		Tuple												=				"Lüsai"
		assert rabin_karp(SCREAMING_SNAKE_CASE_,  SCREAMING_SNAKE_CASE_				)
		__lowercase				:		Union[str, Any]												=				"Lue"
		assert not rabin_karp(SCREAMING_SNAKE_CASE_,  SCREAMING_SNAKE_CASE_				)
		print("Success."				)


if __name__ == "__main__":
						test_rabin_karp()










"""simple docstring"""







class       lowerCAmelCase__       :


				"""simple docstring"""





				def __init__(     self					:	int    ,   lowercase__					:	List[Any]						):
						__lowercase				:		Tuple												=				val
						__lowercase				:		Optional[Any]												=				None
						__lowercase				:		Tuple												=				None



				def       snake_case    (     self					:	Optional[Any]    ,   lowercase__					:	List[str]						):
						if self.val:
								if val < self.val:
										if self.left is None:
												__lowercase				:		Tuple												=				Node(lowercase__						)
										else:
												self.left.insert(lowercase__						)
								elif val > self.val:
										if self.right is None:
												__lowercase				:		Any												=				Node(lowercase__						)
										else:
												self.right.insert(lowercase__						)
						else:
								__lowercase				:		Optional[Any]												=				val





def 						snake_case__       (					_lowerCamelCase,  _lowerCamelCase				)			->Any:






		"""simple docstring"""


		if root:
				inorder(root.left,  _lowerCamelCase				)
				res.append(root.val				)
				inorder(root.right,  _lowerCamelCase				)

def 						snake_case__       (					_lowerCamelCase				)			->Optional[Any]:






		"""simple docstring"""


		if len(_lowerCamelCase				) == 0:
				return arr
		__lowercase				:		int												=				Node(arr[0]				)
		for i in range(1,  len(_lowerCamelCase				)				):
				root.insert(arr[i]				)
		# Traverse BST in order.
		__lowercase				:		Tuple												=				[]
		inorder(_lowerCamelCase,  _lowerCamelCase				)
		return res


if __name__ == "__main__":
						print(tree_sort([1_0, 1, 3, 2, 9, 1_4, 1_3]))
