


def 						__SCREAMING_SNAKE_CASE       (					lowercase_			)		->    list:




						'''simple docstring'''







						__UpperCAmelCase :       Optional[Any]  						=  int(lowercase_			)
						if n_element < 1:
												__UpperCAmelCase :       str  						=  ValueError('''a should be a positive number'''			)
												raise my_error

						__UpperCAmelCase :       Any  						=  [1]
						__UpperCAmelCase						,			__UpperCAmelCase						,			__UpperCAmelCase :       Any  						=  (0, 0, 0)
						__UpperCAmelCase :       int  						=  1
						while index < n_element:
												while hamming_list[i] * 2 <= hamming_list[-1]:
																		i += 1
												while hamming_list[j] * 3 <= hamming_list[-1]:
																		j += 1
												while hamming_list[k] * 5 <= hamming_list[-1]:
																		k += 1
												hamming_list.append(
												    min(hamming_list[i] * 2			,					hamming_list[j] * 3			,					hamming_list[k] * 5			)			)
												index += 1
						return hamming_list


if __name__ == "__main__":
				lowerCAmelCase							=						input("""Enter the last number (nth term) of the Hamming Number Series: """)
				print("""Formula of Hamming Number Series => 2^i * 3^j * 5^k""")
				lowerCAmelCase							=						hamming(int(n))
				print("""-----------------------------------------------------""")
				print(F'The list with nth numbers is: {hamming_numbers}')
				print("""-----------------------------------------------------""")





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()

