Mon Jan 16, 2012 8:06 pm
Admin Với xâu S co trước , ta có thể thực hiện các phép biến đổi sau :
D i : Xóa kí tự vị trí i của xâu S .
I t c : Chèn trước vị trí t của xâu S kí tự c .
R t c : Thay kí tự ở vị trí t của xâu S thành kí tự c .
Cho xâu X và xâu Y . Hãy tìm một dãy phép biến đổi ít nhất để biến xâu X thành xâu Y .
Dữ liệu vào : BDX.INP có cấu trúc
- Dòng 1 : Ghi xâu X .
- Dòng 2 : Ghi xâu Y .
Dữ liệu ra : ghi ra file BDX.OUT có cấu trúc
- Các dòng đầu , mỗi dòng ghi số phép biến đổi theo trình tự để X thành Y .
- Dòng cuối cùng ghi khoảng cách của 2 xâu
vd : BDX.INP
Kitten
sitting
BDX.OUT
I 7 g
R 5 i
R 1 s
3
vd : BDX.INP
Ertrtyui
tyuhj
BDX.OUT
R 8 j
I 8 h
D 4
D 3
D 2
D 1
D i : Xóa kí tự vị trí i của xâu S .
I t c : Chèn trước vị trí t của xâu S kí tự c .
R t c : Thay kí tự ở vị trí t của xâu S thành kí tự c .
Cho xâu X và xâu Y . Hãy tìm một dãy phép biến đổi ít nhất để biến xâu X thành xâu Y .
Dữ liệu vào : BDX.INP có cấu trúc
- Dòng 1 : Ghi xâu X .
- Dòng 2 : Ghi xâu Y .
Dữ liệu ra : ghi ra file BDX.OUT có cấu trúc
- Các dòng đầu , mỗi dòng ghi số phép biến đổi theo trình tự để X thành Y .
- Dòng cuối cùng ghi khoảng cách của 2 xâu
vd : BDX.INP
Kitten
sitting
BDX.OUT
I 7 g
R 5 i
R 1 s
3
vd : BDX.INP
Ertrtyui
tyuhj
BDX.OUT
R 8 j
I 8 h
D 4
D 3
D 2
D 1