BIẾN ĐỔI XÂU (MS0005)VỚI MỘT XÂU KÍ TỰ CHO TRƯỚC, TA CÓ THỂ THỰC HIỆN...

Bài 2: Biến đổi xâu (MS0005)Với một xâu kí tự cho trước, ta có thể thực hiện các phép biến đổi sau: D(i) xóa 1 kí tự tại vị trí i của xâu S I(c,i) chèn kí tự c vào sau kí tự thứ i của xâu S R(i,c) thay kí tự tại vị trí i trong xâu S bởi kí tự CGiả sử X và Y là hai xâu kí tự. Độ dài xâu X là m, độ dài xâu Y là n. hãy tìm một dãy gồm ít nhất các phép biến đổi xâu X thành xâu Y sao cho các phép biến đổi là ít nhất. Số phép biến đổi đó gọi là khoảng cách giữa hai xâuDữ liệu vào ghi trong file XAU.INP gồm 2 dòng Dòng thứ nhất chứa xâu X Dòng thứ nhất chứa xâu YKết quả ghi trong file XAU.OUT gồm Dòng đầu tiên ghi số k là khoảng cách giữa hai xâu K dòng tiếp theo mỗi dòng ghi kí hiệu mỗi phép biến đổi theo trình tự thực hiện biến đổi từ X thành YVí dụ:XAU.INP XAU.OUTERTRTIUI6TIUHJI(J,8)R(8,H)D(4)D(3)D(2)D(1)