TLE-oj Cup Round 5 - Biến đổi xâu

Điểm: 1100 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 128M

Input: TRANS.inp

Output: TRANS.out

Tác giả:

Sunlight

Dạng bài

Cho hai xâu $s$ và $t$ . Với mỗi một thao tác, bạn có thể xóa một ký tự trong $s$ hoặc chèn một ký tự vào vị trí bất kỳ trong $s$ . Đếm số lượng thao tác ít nhất để biến đổi xâu $s$ thành xâu $t$ .

Input, Output và Subtasks

Input: (TRANS.inp)

Dòng đầu tiên chứa xâu ký tự $s$ .
Dòng thứ hai chứa xâu ký tự $t$ .

Output: (TRANS.out)

Một dòng duy nhất là kết quả bài toán.

Subtasks

Subtask 1 $(30\%)$ : Xâu $s$ và xâu $t$ có độ dài không quá $20$ .
Subtask 2 $(30\%)$ : Xâu $s$ và xâu $t$ có độ dài không quá $2000$ .
Subtask 3 $(40\%)$ : Xâu $s$ và xâu $t$ có độ dài không quá $10000$ .

Sample

Input (TRANS.inp)

nguyenkhanhphuc
danghuyhau

Output (TRANS.out)

Notes

Xóa các ký tự thứ $5$ đến thứ $7$ trong xâu $s$ mất ba thao tác, ta được $s =$ nguyhanhphuc.
Chèn các ký tự da vào vị trí đầu tiên của xâu $s$ mất hai thao tác, ta được $s =$ danguyhanhphuc.
Chèn ký tự h vào vị trí thứ $5$ trong xâu $s$ mất một thao tác, ta được $s =$ danghuyhanhphuc.
Xóa các ký tự thứ $14$ đến thứ $17$ trong xâu $s$ mất bốn thao tác, ta được $s =$ danghuyhauc.
Xóa ký tự thứ $12$ trong xâu $s$ mất một thao tác, ta được $s =$ danghuyhau.

Bình luận

Không có bình luận nào.