

'''simple docstring'''

from __future__ import annotations





def       lowercase					(     __magic_name__ ,    __magic_name__							):



					'''simple docstring'''







					UpperCAmelCase		:							List[Any]   					=   get_failure_array(_snake_case							)

					# 2) Step through text searching for pattern
					UpperCAmelCase					, UpperCAmelCase		:							Optional[int]   					=   0, 0  # index into text, pattern
					while i < len(_snake_case							):
										if pattern[j] == text[i]:
															if j == (len(_snake_case							) - 1):
																				return True
															j += 1

										# if this is a prefix in our pattern
										# just go back far enough to continue
										elif j > 0:
															UpperCAmelCase		:							Any   					=   failure[j - 1]
															continue
										i += 1
					return False





def       lowercase					(     __magic_name__							):



					'''simple docstring'''







					UpperCAmelCase		:							Dict   					=   [0]
					UpperCAmelCase		:							List[str]   					=   0
					UpperCAmelCase		:							int   					=   1
					while j < len(_snake_case							):
										if pattern[i] == pattern[j]:
															i += 1
										elif i > 0:
															UpperCAmelCase		:							Dict   					=   failure[i - 1]
															continue
										j += 1
										failure.append(_snake_case							)
					return failure


if __name__ == "__main__":
				# Test 1)
				a   :			Optional[int]         = "abc1abc12"
				a   :			Tuple         = "alskfjaldsabc1abc1abc12k23adsfabcabc"
				a   :			Dict         = "alskfjaldsk23adsfabcabc"
				assert kmp(pattern, texta) and not kmp(pattern, texta)

				# Test 2)
				a   :			int         = "ABABX"
				a   :			str         = "ABABZABABYABABX"
				assert kmp(pattern, text)

				# Test 3)
				a   :			Any         = "AAAB"
				a   :			Any         = "ABAAAAAB"
				assert kmp(pattern, text)

				# Test 4)
				a   :			List[str]         = "abcdabcy"
				a   :			List[Any]         = "abcxabcdabxabcdabcdabcy"
				assert kmp(pattern, text)

				# Test 5)
				a   :			Union[str, Any]         = "aabaabaaa"
				assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]



from __future__ import annotations






def        UpperCamelCase_(							_snake_case   :  int	):




			"""simple docstring"""






			__a        =str(_snake_case	)
			return len(_snake_case	) == 9 and set(_snake_case	) == set('123456789'	)






def        UpperCamelCase_(							):




			"""simple docstring"""






			for base_num in range(9999       ,     4999       ,     -1	):
						__a        =100002 * base_num
						if is_9_pandigital(_snake_case	):
									return candidate

			for base_num in range(333       ,     99       ,     -1	):
						__a        =1002003 * base_num
						if is_9_pandigital(_snake_case	):
									return candidate

			return None


if __name__ == "__main__":
						print(f'''{solution() = }''')






