



"""simple docstring"""

def    __snake_case       (  __A			:	List[str]       ,		__A			:	Dict       ,		__A			:	Union[str, Any]       ,		__A			:	List[str]    )    ->					int:






				'''simple docstring'''
				if start == end:
								return start if lst[start] > item else start + 1
				if start > end:
								return start

				SCREAMING_SNAKE_CASE	:       Any 							=    (start + end) // 2
				if lst[mid] < item:
								return binary_search(__A       ,		__A       ,		mid + 1       ,		__A    )
				elif lst[mid] > item:
								return binary_search(__A       ,		__A       ,		__A       ,		mid - 1    )
				else:
								return mid
def    __snake_case       (  __A			:	Tuple    )    ->					Union[str, Any]:






				'''simple docstring'''
				SCREAMING_SNAKE_CASE	:       Dict 							=    len(__A    )

				for index in range(1       ,		__A    ):
								SCREAMING_SNAKE_CASE	:       str 							=    lst[index]
								SCREAMING_SNAKE_CASE	:       Tuple 							=    binary_search(__A       ,		__A       ,		0       ,		index - 1    )
								SCREAMING_SNAKE_CASE	:       Tuple 							=    lst[:pos] + [value] + lst[pos:index] + lst[index + 1 :]

				return lst
def    __snake_case       (  __A			:	Any       ,		__A			:	List[Any]    )    ->					Optional[int]:






				'''simple docstring'''
				if not left:
								return right

				if not right:
								return left

				if left[0] < right[0]:
								return [left[0], *merge(left[1:]       ,		__A    )]

				return [right[0], *merge(__A       ,		right[1:]    )]
def    __snake_case       (  __A			:	Optional[int]    )    ->					Optional[Any]:






				'''simple docstring'''
				SCREAMING_SNAKE_CASE	:       Optional[int] 							=    len(__A    )
				SCREAMING_SNAKE_CASE							,	SCREAMING_SNAKE_CASE	:       Dict 							=    [], []
				SCREAMING_SNAKE_CASE	:       Any 							=    [lst[0]]
				SCREAMING_SNAKE_CASE	:       List[Any] 							=    []
				SCREAMING_SNAKE_CASE	:       str 							=    1
				while i < length:
								if lst[i] < lst[i - 1]:
												runs.append(__A    )
												SCREAMING_SNAKE_CASE	:       Dict 							=    [lst[i]]
								else:
												new_run.append(lst[i]    )
								i += 1
				runs.append(__A    )

				for run in runs:
								sorted_runs.append(insertion_sort(__A    )    )
				for run in sorted_runs:
								SCREAMING_SNAKE_CASE	:       Dict 							=    merge(__A       ,		__A    )

				return sorted_array
def    __snake_case       (  )    ->					Optional[Any]:






				'''simple docstring'''
				SCREAMING_SNAKE_CASE	:       List[str] 							=    [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
				SCREAMING_SNAKE_CASE	:       List[Any] 							=    tim_sort(__A    )
				print(__A    )


if __name__ == "__main__":
							main()










"""simple docstring"""

def    __snake_case       (  __A			:	str       ,		__A			:	str    )    ->					int:






				'''simple docstring'''
				# The longer word should come first
				if len(__A    ) < len(__A    ):
								return levenshtein_distance(__A       ,		__A    )

				if len(__A    ) == 0:
								return len(__A    )

				SCREAMING_SNAKE_CASE	:       List[Any] 							=    list(range(len(__A    ) + 1    )    )

				for i, ca in enumerate(__A    ):
								SCREAMING_SNAKE_CASE	:       Union[str, Any] 							=    [i + 1]

								for j, ca in enumerate(__A    ):
												# Calculate insertions, deletions and substitutions
												SCREAMING_SNAKE_CASE	:       str 							=    previous_row[j + 1] + 1
												SCREAMING_SNAKE_CASE	:       List[str] 							=    current_row[j] + 1
												SCREAMING_SNAKE_CASE	:       Any 							=    previous_row[j] + (ca != ca)

												# Get the minimum to append to the current row
												current_row.append(min(__A       ,		__A       ,		__A    )    )

								# Store the previous row
								SCREAMING_SNAKE_CASE	:       Tuple 							=    current_row

				# Returns the last element (distance)
				return previous_row[-1]


if __name__ == "__main__":
							A_	:						Optional[int]				=			input('Enter the first word:\n').strip()
							A_	:						Optional[Any]				=			input('Enter the second word:\n').strip()

							A_	:						str				=			levenshtein_distance(first_word, second_word)
							print(f'''Levenshtein distance between {first_word} and {second_word} is {result}''')





