Xâu kí tự!

[tmb12]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Nhập 2 xâu kí tự S1, S2 từ bàn phím, nếu

hãy in ra màn hình xâu ngược của xâu S3

 

[mikelhpdatke]

Bạn có thể lấy một vài ví dụ, một vài tét được ko. Mình băn khoăn chỗ. Giao của S1 và S2 liệu có phải là xâu chung dài nhất (có cả liên tiếp và ko lt) hay chỉ là xâu chung liên tiếp dài nhất

 

[tmb12]

Bạn có thể lấy một vài ví dụ, một vài tét được ko. Mình băn khoăn chỗ. Giao của S1 và S2 liệu có phải là xâu chung dài nhất (có cả liên tiếp và ko lt) hay chỉ là xâu chung liên tiếp dài nhất

Giao của xâu S1 và S2 là xâu chung có các phần tử liên tiếp và không liên tiếp, giống như giao của 2 tập hợp vậy đó

 

[mikelhpdatke]

Thế bạn học QHĐ chưa, bài nay QHĐ là tối ưu nhất, trước tiên mình sẽ chỉ thuật toán cho bạn làm.
Gọi F[i,j] là dộ dài xâu chung dài nhất trong i ký tự đầu của S1 cũng như j ký tự đầu của S2.
Khi đó
F[i,j]:=F[i-1,j-1]+1 nếu S1=S1[j];
F[i,j]:=Max(F[i-1,j],F[i,j-1]) nếu S1<>S1[j].

Truye viết:
Nếu F[i,j]=F[i-1,j-1]+1 thì S3:=S3+S1;dec(i);dec(j);
Còn không thì
Nếu F[i,j]=F[i-1,j] thì dec(i) else dec(j)
Đến khi (i=0) hoặc (j=0);

MÌnh làm hơi vội, có j` sai báo lại

Program Xaukytu;
Var S1,S2,S3:String;
    F:Array[0..100,0..100] Of Integer;
Function Max(a,b:integer):integer;
Begin
 If a>b then max:=a else max:=b;
End;
Procedure Init;
Var i,j:integer;
 Begin
 Readln(s1);
 Readln(s2);
  For i:=0 to length(s1) do
   F[i,0]:=0;
  For j:=0 to length(s2) do
   F[0,j]:=0;

  For i:=1 to length(s1) do
   For j:=1 to length(s2) do
     If S1[i]=S2[j] then
       F[i,j]:=F[i-1,j-1]+1
     Else
       F[i,j]:=Max(F[i-1,j],F[i,j-1]);
 
 S3:='';
   i:=Length(s1);
   j:=Length(s2);
     Repeat
       If F[i,j]=F[i-1,j-1]+1 then begin S3:=S3+S1[i];dec(i);dec(j);end
        Else
          If F[i,j]=F[i-1,j] then dec(i) else dec(j);
     Until (i=0) or (j=0);
 writeln(s3);
End;
BEGIN
Init;
readln
end.