

from __future__ import annotations

def  lowerCamelCase__ (					_a							,			_a):
	SCREAMING_SNAKE_CASE   :      List[Any]				     =       get_failure_array(_a)

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

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

def  lowerCamelCase__ (					_a):
	SCREAMING_SNAKE_CASE   :      Tuple				     =       [0]
	SCREAMING_SNAKE_CASE   :      str				     =       0
	SCREAMING_SNAKE_CASE   :      Dict				     =       1
	while j < len(_a):
		if pattern[i] == pattern[j]:
			i += 1
		elif i > 0:
			SCREAMING_SNAKE_CASE   :      int				     =       failure[i - 1]
			continue
		j += 1
		failure.append(_a)
	return failure


if __name__ == "__main__":
			# Test 1)
			a_						     =    'abc1abc12'
			a_						     =    'alskfjaldsabc1abc1abc12k23adsfabcabc'
			a_						     =    'alskfjaldsk23adsfabcabc'
			assert kmp(pattern, texta) and not kmp(pattern, texta)

			# Test 2)
			a_						     =    'ABABX'
			a_						     =    'ABABZABABYABABX'
			assert kmp(pattern, text)

			# Test 3)
			a_						     =    'AAAB'
			a_						     =    'ABAAAAAB'
			assert kmp(pattern, text)

			# Test 4)
			a_						     =    'abcdabcy'
			a_						     =    'abcxabcdabxabcdabcdabcy'
			assert kmp(pattern, text)

			# Test 5)
			a_						     =    'aabaabaaa'
			assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]


from __future__ import annotations

def  lowerCamelCase__ (					_a							,			_a):
	if b == 0:
		return (1, 0)
	((SCREAMING_SNAKE_CASE)     ,(SCREAMING_SNAKE_CASE))   :      Tuple				     =       extended_euclid(_a							,			a % b)
	SCREAMING_SNAKE_CASE   :      Dict				     =       a // b
	return (y, x - k * y)

def  lowerCamelCase__ (					_a							,			_a							,			_a							,			_a):
	((SCREAMING_SNAKE_CASE)     ,(SCREAMING_SNAKE_CASE))   :      str				     =       extended_euclid(_a							,			_a)
	SCREAMING_SNAKE_CASE   :      str				     =       na * na
	SCREAMING_SNAKE_CASE   :      int				     =       ra * x * na + ra * y * na
	return (n % m + m) % m

def  lowerCamelCase__ (					_a							,			_a):
	((SCREAMING_SNAKE_CASE)     ,(SCREAMING_SNAKE_CASE))   :      List[str]				     =       extended_euclid(_a							,			_a)
	if b < 0:
		SCREAMING_SNAKE_CASE   :      int				     =       (b % n + n) % n
	return b

def  lowerCamelCase__ (					_a							,			_a							,			_a							,			_a):
	SCREAMING_SNAKE_CASE     ,SCREAMING_SNAKE_CASE   :      Dict				     =       invert_modulo(_a							,			_a), invert_modulo(_a							,			_a)
	SCREAMING_SNAKE_CASE   :      Optional[int]				     =       na * na
	SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       ra * x * na + ra * y * na
	return (n % m + m) % m


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

			testmod(name='chinese_remainder_theorem', verbose=True)
			testmod(name='chinese_remainder_theorem2', verbose=True)
			testmod(name='invert_modulo', verbose=True)
			testmod(name='extended_euclid', verbose=True)