Khoảng cách sửa chuỗi

Khó

quy hoạch độngchuỗi6 test · 3 giây

Cần ít nhất bao nhiêu thao tác để biến chuỗi a thành chuỗi b? Mỗi thao tác là một trong:

(Đây là khoảng cách Levenshtein, dùng trong gợi ý sửa lỗi chính tả.)

Dữ liệu vào

Dòng 1: chuỗi a. Dòng 2: chuỗi b. (1 ≤ độ dài ≤ 1500, chữ cái thường)

Số thao tác ít nhất.

Input

horse
ros

Output

horse → rorse → rose → ros

Input

intention
execution

Output

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.