






'''simple docstring'''







from __future__ import annotations





def 		_UpperCAmelCase (				__A				: str    ,		__A				: str   ):
				a_		:	int									=   get_failure_array(__A   )

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





def 		_UpperCAmelCase (				__A				: str   ):
				a_		:	Optional[Any]									=   [0]
				a_		:	Any									=   0
				a_		:	int									=   1
				while j < len(__A   ):
								if pattern[i] == pattern[j]:
												i += 1
								elif i > 0:
												a_		:	List[Any]									=   failure[i - 1]
												continue
								j += 1
								failure.append(__A   )
				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'''







import functools





def 		_UpperCAmelCase (				__A				: list[int]    ,		__A				: list[int]   ):

				# Validation
				if not isinstance(__A    ,		__A   ) or not all(isinstance(__A    ,		__A   ) for day in days   ):
								raise ValueError('''The parameter days should be a list of integers'''   )

				if len(__A   ) != 3 or not all(isinstance(__A    ,		__A   ) for cost in costs   ):
								raise ValueError('''The parameter costs should be a list of three integers'''   )

				if len(__A   ) == 0:
								return 0

				if min(__A   ) <= 0:
								raise ValueError('''All days elements should be greater than 0'''   )

				if max(__A   ) >= 3_66:
								raise ValueError('''All days elements should be less than 366'''   )

				a_		:	List[Any]									=   set(__A   )

				@functools.cache
				def dynamic_programming(__A				: int   ) -> int:
								if index > 3_65:
												return 0

								if index not in days_set:
												return dynamic_programming(index + 1   )

								return min(
								    costs[0] + dynamic_programming(index + 1   )    ,		costs[1] + dynamic_programming(index + 7   )    ,		costs[2] + dynamic_programming(index + 30   )    ,		)

				return dynamic_programming(1   )


if __name__ == "__main__":
		import doctest

		doctest.testmod()




