Cho hai chuỗi ký tự và . Khoảng cách chỉnh sửa (Edit Distance) giữa và là số phép biến đổi ít nhất để biến chuỗi thành chuỗi . Các phép biến đổi được phép là:
Thêm (Insert): Thêm một ký tự vào một vị trí bất kỳ.
Xóa (Delete): Xóa một ký tự ở một vị trí bất kỳ.
Thay thế (Substitute): Thay thế một ký tự bằng một ký tự khác.
Mỗi phép biến đổi có chi phí là . Hãy tính khoảng cách chỉnh sửa giữa hai chuỗi đã cho.
Dữ liệu:
Dòng đầu tiên chứa chuỗi .
Dòng thứ hai chứa chuỗi .
Cả hai chuỗi chỉ chứa các ký tự in hoa ('A'-'Z') và có độ dài từ đến .
Kết quả: Một số nguyên duy nhất là khoảng cách chỉnh sửa giữa và .
Ví dụ:
Dữ liệu:
SUNDAY
SATURDAY
Kết quả:
3
Giải thích: Xóa 2 ký tự A, T và sửa ký tự R thành N trong chuỗi thứ .
