A1.2 Biến đổi xâu ký tự

A1.2 Biến đổi xâu ký tự
Với một xâu ký tự S cho trước, ta có thể thực hiện các phép biến đổi sau:
- D: Xoá một ký tự của xâu S. Ký hiệu D i trong đó i là vị trí cần xóa
- I: Chèn trước vị trí t của xâu S một ký tự c nào đó. Ký hiệu I t c. Qui định thêm về vị trí chèn: nếu xâu S có độ dài k, vị trí chèn là 1, 2, 3, ..., k+1, chèn ở vị trí k+1 có nghĩa là viết thêm vào cuối xâu S
- R: Thay ký tự thứ t của S bởi ký tự c nào đó. Ký hiệu R t c
Giả sử X và Y là hai xâu ký tự. Độ dài xâu X là n, độ dài xâu Y là m (0≤m,n≤100)
Yêu cầu: Hãy tìm một dãy gồm ít nhất các phép biến đổi biến xâu X thành xâu Y (số phép biến đổi ít nhất này gọi là khoảng cách giữa hai xâu).
Dữ liệu: Vào từ tệp CHANGEST.INP gồm hai dòng:
• Dòng thứ nhất là xâu X.
• Dòng thứ hai là xâu Y.
Kết quả: Ghi ra tệp CHANGEST.OUT khoảng cách giữa xâu X và xâu Y.
Ví dụ:
CHANGEST.INP Giải thích
ertrtyui
tyuhj
CHANGEST.OUT

6
Giải thích:
D 1
D 1
D 1
D 1
I 4 h
R 5 j

Thuật toán:
Gọi F[i][j] là số phép biến đổi ít nhất từ X1…Xi thành Y1…Yj
- Kết quả là F[m][n].
- Bài toán cơ sở:
F[0][0]=0;
F[0][j]=j;
F[i][0]=i (với i=1,..,m; j=1,…,n)
+ Công thức qui hoạch độngg:
F[i][j]= F[i-1][j-1] nếu Xi=Yj
F[i][j]= Min(F[i][j-1],F[i-1][j],F[i-1][j-1])+1 nếu Xi!=Yj
Code mẫu