






"""simple docstring"""
from __future__ import annotations






def       __UpperCamelCase						(		snake_case__ , snake_case__       ):
	A_		:    Dict						     = get_failure_array(snake_case__       )

	# 2) Step through text searching for pattern
	A_     ,  A_		:    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:
			A_		:    Union[str, Any]						     = failure[j - 1]
			continue
		i += 1
	return False






def       __UpperCamelCase						(		snake_case__       ):
	A_		:    str						     = [0]
	A_		:    Optional[int]						     = 0
	A_		:    Dict						     = 1
	while j < len(snake_case__       ):
		if pattern[i] == pattern[j]:
			i += 1
		elif i > 0:
			A_		:    Optional[Any]						     = failure[i - 1]
			continue
		j += 1
		failure.append(snake_case__       )
	return failure


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

							# Test 2)
							_lowerCAmelCase       =				"ABABX"
							_lowerCAmelCase       =				"ABABZABABYABABX"
							assert kmp(pattern, text)

							# Test 3)
							_lowerCAmelCase       =				"AAAB"
							_lowerCAmelCase       =				"ABAAAAAB"
							assert kmp(pattern, text)

							# Test 4)
							_lowerCAmelCase       =				"abcdabcy"
							_lowerCAmelCase       =				"abcxabcdabxabcdabcdabcy"
							assert kmp(pattern, text)

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









"""simple docstring"""
def       __UpperCamelCase						(		snake_case__ = 200       ):
	A_		:    Union[str, Any]						     = [1, 2, 5, 10, 20, 50, 100, 200]
	A_		:    int						     = [0] * (pence + 1)
	A_		:    Tuple						     = 1  # base case: 1 way to make 0 pence

	for coin in coins:
		for i in range(snake_case__ , pence + 1 , 1       ):
			number_of_ways[i] += number_of_ways[i - coin]
	return number_of_ways[pence]


if __name__ == "__main__":
							assert solution(200) == 73_682

