




__A						:							Optional[Any]							=  2_5_6
# Modulus to hash a string
__A						:							List[Any]							=  1_0_0_0_0_0_3
def 					lowerCamelCase_    (    SCREAMING_SNAKE_CASE					,	SCREAMING_SNAKE_CASE   ):
			'''simple docstring'''
			SCREAMING_SNAKE_CASE           =					len(SCREAMING_SNAKE_CASE   )
			SCREAMING_SNAKE_CASE           =					len(SCREAMING_SNAKE_CASE   )
			if p_len > t_len:
						return False

			SCREAMING_SNAKE_CASE           =					0
			SCREAMING_SNAKE_CASE           =					0
			SCREAMING_SNAKE_CASE           =					1

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

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

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

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

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


if __name__ == "__main__":
		test_rabin_karp()












def 					lowerCamelCase_    (    SCREAMING_SNAKE_CASE   ):
			'''simple docstring'''
			if not all(char in """01""" for char in bin_string   ):
						raise ValueError("""Non-binary value was passed to the function"""   )
			if not bin_string:
						raise ValueError("""Empty string was passed to the function"""   )
			SCREAMING_SNAKE_CASE           =					""""""
			while len(SCREAMING_SNAKE_CASE   ) % 3 != 0:
						SCREAMING_SNAKE_CASE           =					"""0""" + bin_string
			SCREAMING_SNAKE_CASE           =					[
			    bin_string[index : index + 3]
			    for index in range(len(SCREAMING_SNAKE_CASE   )   )
			    if index % 3 == 0
			]
			for bin_group in bin_string_in_3_list:
						SCREAMING_SNAKE_CASE           =					0
						for index, val in enumerate(SCREAMING_SNAKE_CASE   ):
									oct_val += int(2 ** (2 - index) * int(SCREAMING_SNAKE_CASE   )   )
						oct_string += str(SCREAMING_SNAKE_CASE   )
			return oct_string


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

		testmod()






