


"""simple docstring"""
__SCREAMING_SNAKE_CASE							:      Optional[Any]						=      256
# Modulus to hash a string
__SCREAMING_SNAKE_CASE							:      Optional[int]						=      1_000_003







def   _a			( _SCREAMING_SNAKE_CASE			,	_SCREAMING_SNAKE_CASE			)      ->			bool:
							snake_case_          =						len(_SCREAMING_SNAKE_CASE			)
							snake_case_          =						len(_SCREAMING_SNAKE_CASE			)
							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(_SCREAMING_SNAKE_CASE			):
														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   _a			( )      ->			None:
							snake_case_          =						"""abc1abc12"""
							snake_case_          =						"""alskfjaldsabc1abc1abc12k23adsfabcabc"""
							snake_case_          =						"""alskfjaldsk23adsfabcabc"""
							assert rabin_karp(_SCREAMING_SNAKE_CASE			,	_SCREAMING_SNAKE_CASE			) and not rabin_karp(_SCREAMING_SNAKE_CASE			,	_SCREAMING_SNAKE_CASE			)

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

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

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

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


if __name__ == "__main__":
				test_rabin_karp()







"""simple docstring"""
def   _a			( _SCREAMING_SNAKE_CASE			)      ->			int:
							assert column_title.isupper()
							snake_case_          =						0
							snake_case_          =						len(_SCREAMING_SNAKE_CASE			) - 1
							snake_case_          =						0

							while index >= 0:
														snake_case_          =						(ord(column_title[index]			) - 64) * pow(26			,	_SCREAMING_SNAKE_CASE			)
														answer += value
														power += 1
														index -= 1

							return answer


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

				testmod()



