



import math

def        __a			(   __lowerCAmelCase   )     ->     bool:
					assert isinstance(__lowerCAmelCase      ,	__lowerCAmelCase   ) and (
					    number >= 0
					), "'number' must been an int and positive"

					if 1 < number < 4:
										# 2 and 3 are primes
										return True
					elif number < 2 or not number % 2:
										# Negatives, 0, 1 and all even numbers are not primes
										return False

					SCREAMING_SNAKE_CASE							:     List[Any]						=				range(3      ,	int(math.sqrt(__lowerCAmelCase   ) + 1   )      ,	2   )
					return not any(not number % i for i in odd_numbers   )



def        __a			(   __lowerCAmelCase      ,	__lowerCAmelCase=1      ,	**__lowerCAmelCase   )     ->     List[str]:
					SCREAMING_SNAKE_CASE							:     Union[str, Any]						=				factor * value
					SCREAMING_SNAKE_CASE							:     List[str]						=				value

					while not is_prime(__lowerCAmelCase   ):
										value += 1 if not ("desc" in kwargs and kwargs["desc"] is True) else -1

					if value == first_value_val:
										return next_prime(value + 1      ,	**__lowerCAmelCase   )
					return value




_lowerCamelCase    :		Optional[Any]		      =    256
# Modulus to hash a string
_lowerCamelCase    :		Optional[Any]		      =    1_000_003

def        __a			(   __lowerCAmelCase      ,	__lowerCAmelCase   )     ->     bool:
					SCREAMING_SNAKE_CASE							:     Tuple						=				len(__lowerCAmelCase   )
					SCREAMING_SNAKE_CASE							:     Tuple						=				len(__lowerCAmelCase   )
					if p_len > t_len:
										return False

					SCREAMING_SNAKE_CASE							:     Dict						=				0
					SCREAMING_SNAKE_CASE							:     Tuple						=				0
					SCREAMING_SNAKE_CASE							:     Optional[Any]						=				1

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

def        __a			(   )     ->     None:
					SCREAMING_SNAKE_CASE							:     Any						=				'abc1abc12'
					SCREAMING_SNAKE_CASE							:     str						=				'alskfjaldsabc1abc1abc12k23adsfabcabc'
					SCREAMING_SNAKE_CASE							:     List[str]						=				'alskfjaldsk23adsfabcabc'
					assert rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   ) and not rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   )

					# Test 2)
					SCREAMING_SNAKE_CASE							:     List[str]						=				'ABABX'
					SCREAMING_SNAKE_CASE							:     int						=				'ABABZABABYABABX'
					assert rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   )

					# Test 3)
					SCREAMING_SNAKE_CASE							:     int						=				'AAAB'
					SCREAMING_SNAKE_CASE							:     Tuple						=				'ABAAAAAB'
					assert rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   )

					# Test 4)
					SCREAMING_SNAKE_CASE							:     Tuple						=				'abcdabcy'
					SCREAMING_SNAKE_CASE							:     Optional[Any]						=				'abcxabcdabxabcdabcdabcy'
					assert rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   )

					# Test 5)
					SCREAMING_SNAKE_CASE							:     List[Any]						=				'Lü'
					SCREAMING_SNAKE_CASE							:     Optional[Any]						=				'Lüsai'
					assert rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   )
					SCREAMING_SNAKE_CASE							:     Union[str, Any]						=				'Lue'
					assert not rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   )
					print('Success.'   )


if __name__ == "__main__":
			test_rabin_karp()