KHOẢNG CÁCH GIỮA HAI XÂUCHO HAI XÂU KÝ TỰ S1 VÀÌ S2 MỖI XÂU CÓ ĐỘ...

4. Xóa bớt một ký tự.

Ta gọi khoảng cách giữa hai xâu S

1

và S

2

là số nhỏ nhất các phép biến đổi

nêu trên cần áp dụng đối với xâu S

1

để biến nó thành xâu S

2

.

Yêu cầu : Tính khoảng cách giữa hai xâu S

1

và S

2

cho trước.

Ví dụ : giả sử S

1

= ‘Barney’ S

2

=’brawny’ . Khoảng cách giữa hai xâu S

1

và S

2

là 4.

Dãy các phép biến đổi cần thực hiện là :

-Thay kí tự của S

1

: ‘B’ bởi ‘b’ ;

-Đổi chỗ hai ký tự thứ hai (‘a’)và thứ ba (‘r’) ;

-Chèn ký tự ‘w’ vào sau ký tự thứ ba;

-Xóa ký tự thứ năm.

Dãy phép biến đổi có thể mô tả như sau :

‘Barney’  ‘barney’  ‘braney’  ‘brawney’  ‘brawny’

Dữ liệu : vào từ file văn bản BIENDOI.INP có cấu trúc như sau :

. Dòng đầu tiên chứa xâu S

1

. Dòng thứ hai chứa xâu S

2

Kết quả : Ghi ra file văn bản BIENDOI.OUT

. Dòng đầu tiên ghi số lượng phép biến đổi cần sử dụng (gọi là k).

. Mỗi dòng thứ i trong số k dòng tiếp theo mô tả phép biến đổi được sử

dụng ở lần thứ i(i=1,2,...,k) ; đầu tiên ghi chỉ số của phép biến đổi được sử dụng,

tiếp đến :

+ Nếu là phép biến đổi 1 cần chỉ ra vị trí của các ký tự cần thay thế trong

xâu đang biến đổi và ký tự thay thế ;

+ Nếu là phép biến đổi 2 cần chỉ ra vị trí (xếp theo thứ tự tăng dần) của

hai ký tự cần đổi chỗ;

+ Nếu là phép biến đổi 3 cần chỉ ra vị trí của ký tự trong xâu đang xét mà

sau nó cần chèn một ký tự và ký tự cần chèn ;

+ Nếu là phép biến đổi 4 cần chỉ ra vị trí của ký tự cần xóa trong câu đang

xét.

Ví dụ :