Khoảng cách chỉnh sửa

General
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho hai xâu ký tự $S$ và $T$. Bạn có thể thực hiện 3 loại phép biến đổi trên xâu $S$:

  1. Chèn một ký tự vào vị trí bất kỳ.
  2. Xóa một ký tự.
  3. Thay thế một ký tự bằng ký tự khác.

Hãy tìm số phép biến đổi ít nhất để biến xâu $S$ thành xâu $T$.

Dữ liệu vào
  • Dòng đầu chứa xâu $S$ ($1 \le |S| \le 2000$).
  • Dòng thứ hai chứa xâu $T$ ($1 \le |T| \le 2000$).
Dữ liệu ra

Một số nguyên duy nhất là số phép biến đổi ít nhất.

Ví dụ
Input Output
horse<br>ros 3
Giới hạn
  • $1 \le |S|, |T| \le 2000$
Draft saved