Khoảng cách so với xâu palindrome

[thoitrangpk]

Ta định nghĩa khoảng cách giữa hai xâu là số lần xóa hoặc thay thế hoặc thêm vào một ký tự của xâu này để được xâu kia với điều kiện số lần thực hiện là ít nhất. Ta luyện tập chút ít nhé! Nào, hãy tìm khoảng cách giữa một xâu s1 và xâu palidrome tạo thành từ s1. Quy ước:
- Xóa kí tự thứ k: del(k).
- Thêm kí tự thứ k: ins(k).
- Thay thế kí tự thứ k bằng kí tự x: replace(k,x).
INPUT:
Một dòng là xâu s1.
OUTPUT:
- Dòng một in khoảng cách n.
- N+1 dòng tiếp theo là các phép biến đổi từ s1->palidrome.
Nào ta cùng luyện tập!

[dongeriko]

Quy hoạch động f[i,j] là số thao tác ít nhất để đoạn từ i->j thành palin

[taitrochoifree11]

Bạn vít thế thì mỗi bạn hỉu thui. Qhd có cơ sở qhd mà, khôg cho thì ai mà bít.

[quy263]

http://diendantinhoc.vn/showthread.php?p=81531#post81531

còn mỗi phần truy vết thôi !!!

[komoro92]

http://diendantinhoc.vn/showthread.php?p=81531#post81531

còn mỗi phần truy vết thôi !!!

Elnino trích link mình không hiểu mục đích làm, bài này làm theo quy hoạch động là đúng đắn rồi. Kết hợp giũa khoảng cách xâu và palidrome.

[ngoduong]

sao ko giai bai nay lun di?
goi y kiu do ai ma ko bit chu

[mallboro]

"Khoảng cách" giữa 2 xâu kí tự.

Giả sử với một xâu kí tự, ta có thể tiến hành các phép biến đổi sau:

• Thay một kí tự bất kì bởi một kí tự khác, chẳng hạn: test -> text;
• Xóa một kí tự bất kì, chẳng hạn: text -> ext hoặc text -> txt;
• Thêm một kí tự bất kì vào một vị trí bất kì, chẳng hạn: SP -> SP2;

Với 2 xâu S1 và S2, ta nói "khoảng cách" từ S1 đến S2 bằng số lượng ít nhất các phép biến đổi thuộc 3 loại trên mà khi áp dụng liên tiếp vào S1 ta sẽ nhận được S2.

Dữ liệu vào được cho bởi file văn bản DISTANCE.INP gồm 2 dòng, dòng 1 là xâu S1, dòng 2 là xâu S2 (S1, S2 xâu có không quá 100 kí tự).

Kết quả ghi ra file văn bẳn DISTANCE.OUT như sau: dòng đầu là khoảng cách từ S1 đến S2, các dòng còn lại, mỗi dòng ghi một phép biến đổi theo thứ tự từ S1 có được S2.
Ví dụ:

	

		

			

			
				DISTANCE.INP
1A3BC
13Ab
			
		
	

	

		

			

			
				DISTANCE.OUT
3
1A3BC - Thay C/5/b => 1A3Bb
1A3Bb - Thay B/4/A => 1A3Ab
1A3Ab - Xoa A/2 => 13Ab
			
		
	

{+B-, Q+, R+}
{$M 65500, 0, 655360}
Uses Crt;

Const MaxN = 100;
      fi = 'DISTANCE.INP';
      fo = 'DISTANCE.OUT';

Type xau = String[MaxN];
     AByte = Array[0..MaxN, 0..MaxN] Of Byte;

Var a, b : xau;     q : AByte;
    m, n : Byte;
    f : Text;

Procedure KhoiTao;
Begin
     Assign(f, fi);
     Reset(f);
     Readln(f, a);
     Readln(f, b);
     m := Length(a);
     n := Length(b);
     Close(f);
End;

Function Min(a, b, c : Byte) : Byte;
Begin
     If a > b Then a := b;
     If a > c Then a := c;
     Min := a;
End;

Procedure InMang;
Var i, j : Byte;
Begin
     Writeln('A = ',a);
     Writeln('B = ',b);
     Write(#32 : 4);
     For i := 1 To n Do Write(b[i] : 3);
     Writeln(#10#13);
     For i := 1 To m Do
     Begin
          Write(a[i] : 3, #32);
          For j := 1 To n Do Write(q[i, j] : 3);
          Writeln;
     End;
End;

Procedure TaoQHD;
Var i, j, dt : Byte;
    ok : Boolean;
Begin
     For i := 1 To m Do q[i, 0] := i;
     For j := 1 To n Do q[0, j] := j;
     q[0, 0] := 0;
     For i := 1 To m Do
          For j := 1 To n Do
          Begin
               If a[i] = b[j] Then dt := 0
               Else dt := 1;
               q[i, j] := Min(q[i-1, j-1] + dt, q[i-1, j] + 1, q[i, j-1] + 1);
          End;
End;

Procedure LanNguoc;
Var i, j, gt : Byte;
Begin
     i := m;
     j := n;
     While (i > 0) And (j > 0) And (q[i, j] <> 0) Do
     Begin
          gt := q[i, j] - 1;
          If q[i-1, j-1] = gt Then
          Begin
               Write(f, a, ' - ');
               Write(f, 'Thay ', a[i], '/', i, '/', b[j]);
               a[i] := b[j];
               Writeln(f, ' => ', a);
               Dec(i); Dec(j);
          End
          Else
               If q[i-1, j] = gt Then
               Begin
                    Write(f, a, ' - ');
                    Write(f, 'Xoa ', a[i], '/', i);
                    Delete(a, i, 1);
                    Writeln(f, ' => ', a);
                    Dec(i);

               End
               Else
                    If q[i, j-1] = gt Then
                    Begin
                         Write(f, a, ' - ');
                         Write(f, 'Them ', b[j], '/', i+1);
                         Insert(b[j], a, i+1);
                         Writeln(f, ' => ', a);
                         Dec(j);
                    End
                    Else
                         If q[i, j] = q[i-1, j-1] Then
                         Begin
                              Dec(i); Dec(j);
                         End;
     End;
     If (i = 0) And (j <> 0) Then
     For i := j DownTo 1 Do
     Begin
          Write(f, a, ' - ');
          Write(f, 'Them ', b[i], '/', 1);
          Insert(b[i], a, 1);
          Writeln(f, ' => ', a);
     End
     Else
          If (j = 0) And (i <> 0) Then
          Begin
               For j := i DownTo 1 Do
               Begin
                    Write(f, a, ' - ');
                    Write(f, 'Xoa ', a[1], '/', 1);
                    Delete(a, 1, 1);
                    Writeln(f, ' => ', a);
               End;
          End;
End;

Procedure Xuly;
Begin
     TaoQHD;
     InMang;
     Assign(f, fo);
     Rewrite(f);
     Writeln(f, q[m, n]);
     LanNguoc;
     Close(f);
End;

BEGIN
     KhoiTao;
     Xuly;
END.

[teenddeem]

Thế nếu thêm 1 cách biển đổi nữa là đổi chỗ 2 kí tự liên tiếp thì phần code thay đổi thế nào?