



'''simple docstring'''





def   _SCREAMING_SNAKE_CASE    (			UpperCamelCase     ):



    """simple docstring"""





    if collection == []:
        return []

    # get some information about the collection
    lowerCAmelCase__					:    Tuple				 =   len(__A     )
    lowerCAmelCase__					:    Union[str, Any]				 =   max(__A     )
    lowerCAmelCase__					:    List[Any]				 =   min(__A     )

    # create the counting array
    lowerCAmelCase__					:    List[Any]				 =   coll_max + 1 - coll_min
    lowerCAmelCase__					:    Any				 =   [0] * counting_arr_length

    # count how much a number appears in the collection
    for number in collection:
        counting_arr[number - coll_min] += 1

    # sum each position with it's predecessors. now, counting_arr[i] tells
    # us how many elements <= i has in the collection
    for i in range(1				,       __A     ):
        lowerCAmelCase__					:    str				 =   counting_arr[i] + counting_arr[i - 1]

    # create the output collection
    lowerCAmelCase__					:    Tuple				 =   [0] * coll_len

    # place the elements in the output, respecting the original order (stable
    # sort) from end to begin, updating counting_arr
    for i in reversed(range(0				,       __A     )     ):
        lowerCAmelCase__					:    int				 =   collection[i]
        counting_arr[collection[i] - coll_min] -= 1

    return ordered
def   _SCREAMING_SNAKE_CASE    (			UpperCamelCase     ):



    """simple docstring"""





    return "".join([chr(__A     ) for i in counting_sort([ord(__A     ) for c in string]     )]     )


if __name__ == "__main__":
 # Test string sort
 assert counting_sort_string('''thisisthestring''') == "eghhiiinrsssttt"

 _lowerCAmelCase 		=      input('''Enter numbers separated by a comma:\n''').strip()
 _lowerCAmelCase 		=      [int(item) for item in user_input.split(''',''')]
 print(counting_sort(unsorted))










'''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]




