Problem
Cho một chuỗi văn bản. Bạn có thể thực hiện các thao tác sau với nó:
1. Thay thế một ký tự của chuỗi bằng một ký tự khác.
2. Xóa một ký tự tùy ý.
3. Chèn một ký tự tùy ý vào vị trí tùy ý trong chuỗi.
Ví dụ: sử dụng thao tác đầu tiên từ chuỗi "JUICE" bạn có thể lấy chuỗi "SUK", sử dụng thao tác thứ hai - chuỗi "OK", sử dụng thao tác thứ ba - chuỗi "STOCK.
Số lượng thao tác tối thiểu như vậy có thể được sử dụng để lấy một chuỗi khác từ một chuỗi được gọi là chi phí chỉnh sửa hoặc khoảng cách Levenshtein.
Tìm khoảng cách Levenshtein cho hai chuỗi đã cho.
Đầu vào
Chương trình nhận hai chuỗi làm đầu vào, độ dài của mỗi chuỗi không vượt quá 1000 ký tự, các chuỗi chỉ bao gồm các chữ cái Latinh viết hoa.
Đầu ra
Bắt buộc phải xuất một số duy nhất – Khoảng cách Levenshtein cho các chuỗi đã cho.
| Đầu vào |
Đầu ra |
|
ABCDEFGH
ACDEXGIH
|
3 |