

'''simple docstring'''





from __future__ import annotations







def   _UpperCamelCase	(		__UpperCamelCase    ,__UpperCamelCase	)       ->			bool:
					lowerCamelCase_  				=      get_failure_array(__UpperCamelCase	)

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

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







def   _UpperCamelCase	(		__UpperCamelCase	)       ->			list[int]:
					lowerCamelCase_  				=      [0]
					lowerCamelCase_  				=      0
					lowerCamelCase_  				=      1
					while j < len(__UpperCamelCase	):
										if pattern[i] == pattern[j]:
															i += 1
										elif i > 0:
															lowerCamelCase_  				=      failure[i - 1]
															continue
										j += 1
										failure.append(__UpperCamelCase	)
					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]






'''simple docstring'''



def       snake_case   (	snake_case      : list			) ->  list:


    """simple docstring"""


    if any(not isinstance(snake_case					,		snake_case			) or x < 0 for x in sequence			):
        raise TypeError('Sequence must be list of non-negative integers'			)
    for _ in range(len(snake_case			)			):
        for i, (rod_upper, rod_lower) in enumerate(zip(snake_case					,		sequence[1:]			)			):
            if rod_upper > rod_lower:
                sequence[i] -= rod_upper - rod_lower
                sequence[i + 1] += rod_upper - rod_lower
    return sequence


if __name__ == "__main__":
     assert bead_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
     assert bead_sort([7, 9, 4, 3, 5]) == [3, 4, 5, 7, 9]





