ĐỀ THI HỌC SINH GIỎI

Cho xâu ký tự X, xét 3 phép biến đổi:

a) Insert(i, C): i là số, C là ký tự: Phép Insert chèn ký tự C vào sau vị trí i của xâu X.

b) Replace(i, C): i là số, C là ký tự: Phép Replace thay ký tự tại vị trí i của xâu X bởi ký tự C.

c) Delete(i): i là số, Phép Delete xoá ký tự tại vị trí i của xâu X.

Yêu cầu: Cho trước xâu Y, hãy tìm một số ít nhất các phép biến đổi trên để biến xâu X thành xâu Y.

Input: file văn bản STR.INP

• Dòng 1: Chứa xâu X (độ dài ≤ 100)

• Dòng 2: Chứa xâu Y (độ dài ≤ 100)

Output: file văn bản STR.OUT ghi các phép biến đổi cần thực hiện và xâu X tại mỗi phép biến đổi.
Ví dụ
+Tệp STR.INP có hai dòng như sau:
PBBCEFATZ
QABCDABEFA
+Tệp STR.OUT có kết quả như sau:
7
PBBCEFATZ -> Delete(9) -> PBBCEFAT
PBBCEFAT -> Delete(8) -> PBBCEFA
PBBCEFA -> Insert(4, B) -> PBBCBEFA
PBBCBEFA -> Insert(4, A) -> PBBCABEFA
PBBCABEFA -> Insert(4, D) -> PBBCDABEFA
PBBCDABEFA -> Replace(2, A) -> PABCDABEFA
PABCDABEFA -> Replace(1, Q) -> QABCDABEFA
Gửi kết quả nhanh lên