


def 						__SCREAMING_SNAKE_CASE       (					lowercase_			,					lowercase_ = False			)		->    bool:




						'''simple docstring'''







						if n == 2:
												return True
						if not n % 2 or n < 2:
												return False
						if n > 5 and n % 10 not in (1, 3, 7, 9):  # can quickly check last digit
												return False
						if n > 3317044064679887385961981 and not allow_probable:
												raise ValueError(
												    '''Warning: upper bound of deterministic test is exceeded. '''
												    '''Pass allow_probable=True to allow probabilistic test. '''
												    '''A return value of True indicates a probable prime.'''			)
						# array bounds provided by analysis
						__UpperCAmelCase :       Optional[int]  						=  [
						    2047,
						    1373653,
						    25326001,
						    3215031751,
						    2152302898747,
						    3474749660383,
						    341550071728321,
						    1,
						    3825123056546413051,
						    1,
						    1,
						    318665857834031151167461,
						    3317044064679887385961981,
						]

						__UpperCAmelCase :       Union[str, Any]  						=  [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
						for idx, _p in enumerate(lowercase_			,					1			):
												if n < _p:
																		# then we have our last prime to check
																		__UpperCAmelCase :       Optional[Any]  						=  primes[:idx]
																		break
						__UpperCAmelCase						,			__UpperCAmelCase :       Dict  						=  n - 1, 0
						# break up n -1 into a power of 2 (s) and
						# remaining odd component
						# essentially, solve for d * 2 ** s == n - 1
						while d % 2 == 0:
												d //= 2
												s += 1
						for prime in plist:
												__UpperCAmelCase :       Union[str, Any]  						=  False
												for r in range(lowercase_			):
																		__UpperCAmelCase :       Dict  						=  pow(lowercase_			,					d * 2**r			,					lowercase_			)
																		# see article for analysis explanation for m
																		if (r == 0 and m == 1) or ((m + 1) % n == 0):
																								__UpperCAmelCase :       Optional[Any]  						=  True
																								# this loop will not determine compositeness
																								break
												if pr:
																		continue
												# if pr is False, then the above loop never evaluated to true,
												# and the n MUST be composite
												return False
						return True




def 						__SCREAMING_SNAKE_CASE       (					)		->    None:




						'''simple docstring'''







						assert not miller_rabin(561			)
						assert miller_rabin(563			)
						# 2047

						assert not miller_rabin(838201			)
						assert miller_rabin(838207			)
						# 1_373_653

						assert not miller_rabin(17316001			)
						assert miller_rabin(17316017			)
						# 25_326_001

						assert not miller_rabin(3078386641			)
						assert miller_rabin(3078386653			)
						# 3_215_031_751

						assert not miller_rabin(1713045574801			)
						assert miller_rabin(1713045574819			)
						# 2_152_302_898_747

						assert not miller_rabin(2779799728307			)
						assert miller_rabin(2779799728327			)
						# 3_474_749_660_383

						assert not miller_rabin(113850023909441			)
						assert miller_rabin(113850023909527			)
						# 341_550_071_728_321

						assert not miller_rabin(1275041018848804351			)
						assert miller_rabin(1275041018848804391			)
						# 3_825_123_056_546_413_051

						assert not miller_rabin(79666464458507787791867			)
						assert miller_rabin(79666464458507787791951			)
						# 318_665_857_834_031_151_167_461

						assert not miller_rabin(552840677446647897660333			)
						assert miller_rabin(552840677446647897660359			)
						# 3_317_044_064_679_887_385_961_981
						# upper limit for probabilistic test


if __name__ == "__main__":
				test_miller_rabin()





lowerCAmelCase							=						256
# Modulus to hash a string
lowerCAmelCase							=						1_000_003




def 						__SCREAMING_SNAKE_CASE       (					lowercase_			,					lowercase_			)		->    bool:




						'''simple docstring'''







						__UpperCAmelCase :       List[str]  						=  len(lowercase_			)
						__UpperCAmelCase :       Tuple  						=  len(lowercase_			)
						if p_len > t_len:
												return False

						__UpperCAmelCase :       Any  						=  0
						__UpperCAmelCase :       List[Any]  						=  0
						__UpperCAmelCase :       List[Any]  						=  1

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




def 						__SCREAMING_SNAKE_CASE       (					)		->    None:




						'''simple docstring'''







						__UpperCAmelCase :       Optional[int]  						=  '''abc1abc12'''
						__UpperCAmelCase :       List[str]  						=  '''alskfjaldsabc1abc1abc12k23adsfabcabc'''
						__UpperCAmelCase :       Any  						=  '''alskfjaldsk23adsfabcabc'''
						assert rabin_karp(lowercase_			,					lowercase_			) and not rabin_karp(lowercase_			,					lowercase_			)

						# Test 2)
						__UpperCAmelCase :       Union[str, Any]  						=  '''ABABX'''
						__UpperCAmelCase :       List[Any]  						=  '''ABABZABABYABABX'''
						assert rabin_karp(lowercase_			,					lowercase_			)

						# Test 3)
						__UpperCAmelCase :       str  						=  '''AAAB'''
						__UpperCAmelCase :       List[Any]  						=  '''ABAAAAAB'''
						assert rabin_karp(lowercase_			,					lowercase_			)

						# Test 4)
						__UpperCAmelCase :       Optional[Any]  						=  '''abcdabcy'''
						__UpperCAmelCase :       Any  						=  '''abcxabcdabxabcdabcdabcy'''
						assert rabin_karp(lowercase_			,					lowercase_			)

						# Test 5)
						__UpperCAmelCase :       Any  						=  '''Lü'''
						__UpperCAmelCase :       Optional[int]  						=  '''Lüsai'''
						assert rabin_karp(lowercase_			,					lowercase_			)
						__UpperCAmelCase :       List[Any]  						=  '''Lue'''
						assert not rabin_karp(lowercase_			,					lowercase_			)
						print('''Success.'''			)


if __name__ == "__main__":
				test_rabin_karp()

