# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  Help me! Xâu con chung dài nhất

## poodle

Tìm dãy con chung dài nhất của string S1 S2 cho trước trong xaucon.inp:
- Dòng thứ nhất ghi s1.
- Dòng thứ hai ghi s2.
File out xaucon.out:
1 dòng duy nhất ghi xâu con chung dài nhất (nếu không có ghi 0)
Các bạn có phương pháp giải nào dễ hiểu post lên giúp mình với. Cách giải tốt hơn code, mình đọc code chậm hiểu lắm :emlaugh:

----------


## ngoclongnb1609

bài này áh , sách LMH có hướng dẫn cụ thể ùi mà . Bài này giống bài dãy con chung dài nhất của 2 mảng í - bài tập phần QHĐ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] . Thay mảng = xâu thôi .

----------


## quynhvunb

*Chương Trình:*



> .ProGram _FindMaxString;
> .Var InpFile, OutFile ; Text;
> . S1, S2 : String;
> .Func Find( Str1,Str2 : String; ) : String;
> . Var i,j : integer;
> . Str : String;
> . BeGin
> . For i := 1 To Length( Str1 ) Do
> . For j := 1 To Length( Str2) - Length( Str1 ) Do
> ...


*Thuật Toán:*
Ở đây mình tạo 1 hàm cho chương trình để tìm dãy chung lớn nhất của 2 xâu.
Hàm Find Nhận đầu vào là 2 Xâu : Str1 ,Str2 ( ở đây, xâu Str1 phải bé hơn xâu Str2)
Ta Dùng 2 Vòng lặp For để tạo lần lượt các xâu chung Str:



> . For i := 1 To Length( Str1 ) Do
> . For j := 1 To Length( Str2) - i Do
> . BeGin
> . Str := Copy(Str1, i, j);
> . If Pos( Str, Str2) Then 
> . Find := Str
> . Else 
> . Find := '';
> . End;
> . End;


Biến i là độ dài của Xâu Chung Str : Cho i Tăng dần từ 1 (nhỏ nhất) đến Length( Str1 ) ( Lớn nhất).
Biến j là vị trí của xâu chung Str trong xâu Str1 : Cho j tăng dần từ 1 ( vị trí đầu tiên của xâu chung Str trong xâu Str1) đến Length( Str2) - i ( vị trí cuối cùng của xâu chung Str trong xâu Str1, vì độ dài của xâu chung là i nên số các vị trí xuất hiện của xâu chung trong xâu Str1 = Length( Str2) - i ). Ta dùng Hàm Copy(Str1, i, j) để Tạo Xâu chung Str : Xâu chung Str = Copy trong xâu Str1 i kí tự , bắt đầu từ vị trí j.
Có được xâu chung Str, Ta dùng Hàm Post(Str, Str2) để kiểm tra xâu chung Str có tồn tại trong xâu Str1 không. Nếu có, giá trị trả về của hàm Find là xâu Str, nếu không là xâu rỗng ( '' ). Vì Biến i -độ dài của Xâu Chung Str trong vòng lặp luôn tăng nên độ lớn xâu chung cuối cùng nhận được mà hàm trả về sẽ là lớn nhất.
======================================
Xong phần hàm. Ta đền thân chương trình.
Phần việc còn lại của thân chương trình là tìm ra xâu bé hơn và xâu lớn hơn trong 2 xâu ta nhận được từ tệp xaucon.inp để ta dùng hàm Find ( vì hàm Find yêu cầu xâu Str1 là xâu bé hơn).Ta dùng câu lệnh If:



> . If S1 <= S2 Then
> . Write(OutFile,Find(S1,S2))
> . Else
> . Write(OutFile,Find(S2,S1));


Mọi thứ còn lại bạn cứ đọc Code để tìm hiểu, Bài này chỉ là một cách để bạn tham khảo thôi, lời giải thích của mình hơi khó hỉu ( Dốt Văn mà:a[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] , cố gắn hiểu nha. G:1eye:1eyed Luck

_( Lâu nay không viết code pascal nên quên chút chút, Bạn đọc nếu có lỗi cú pháp thì Edit giúp ^^!)._

----------


## hoangkiso

Bạn giải chỗ Pos(s1,s2) tui không hiểu, đề nghị cung cấp code chạy được hoặc phương pháp giải

----------


## Nlseo01

Hàm Pos(S1, S2); Là hàm cho vị trí xuất hiện đầu tiên của xâu S1 Trong xâu S2, nếu không xuất hiện thì trả về giá trị 0.
*Code:* Code này tìm ra xâu dài nhất, nếu có hơn một xâu dài nhất, sẽ lấy xâu lớn hơn( bằng cách so sánh mã ASCII).



> ProGram Xau_Chung_Lon_Nhat;
> 
> Var S1, S2, Max_Str : String;
> InpFile, OutFile : Text;
> Function Check_Exists( S1, S2 : String) : String;
> Var i, j : Integer;
> XauChung, SubStr : String;
> Begin
> For i := 1 To Length(S1) Do
> ...


Code đã Check, hiện mình chưa thấy lỗi, Sr. mình không bt nói cách nào cho rõ thuật toán, Bạn chịu khó xem code vậy nha.

----------


## ngoduong

> Hàm Pos(S1, S2); Là hàm cho vị trí xuất hiện đầu tiên của xâu S1 Trong xâu S2, nếu không xuất hiện thì trả về giá trị 0.


 Bạn giải thích rõ được không, mình không hiểu#-o, hàm trả về mang giá trị gì? Số à? "cho vị trí xuất hiện đầu tiên của xâu S1 Trong xâu S2", không hiểu[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## yurycandy

nếu xâu s1 xuất hiện trong xâu s2 thì hàm pos ( s1 , s2 ) sẽ cho giá trị là vị trí đầu tiên của s2 trong s1 
s1 : ab
s2 : cdabfg
-> pos ( s1,s2) = 3
nếu xâu s1 k xuất hiện trong xâu s2 thì hàm pos ( s1,s2 ) cho giá trị = 0
s1 : ab
s2 : ponmeh 
-> pos (s1,s2) =0

----------


## annkhsouth

À, hiểu, để mình nghiên cứu code xem sao:whistling:

----------


## ngoclongnb1609

Tức là nó tìm S1 là tập con của S2 ấy. Bác tiếp tục đọc và học đi nhé. Chúc vui!

----------


## actech1

> nếu xâu s1 xuất hiện trong xâu s2 thì hàm pos ( s1 , s2 ) sẽ cho giá trị là vị trí đầu tiên của s2 trong s1 
> s1 : ab
> s2 : cdabfg
> -> pos ( s1,s2) = 3
> nếu xâu s1 k xuất hiện trong xâu s2 thì hàm pos ( s1,s2 ) cho giá trị = 0
> s1 : ab
> s2 : ponmeh 
> -> pos (s1,s2) =0


Lời giải thích này có vẻ hoàn hảo rồi đấy, mình không bt nói gì thêm hết, chúc các bạn học tốt Pascal, có gì cứ Post lên, nếu bt thì mình giúp....

----------


## minhle107

Tạm thời mình chưa hiểu cách làm, nhưng bạn xem lại test: s1=zabcef;s2=ceabckef;
Test sai :bored:
Bạn post code chạy hoàn chỉnh đi, mình đọc code hoàn chỉnh hoặc cách giải mới hiểu:wacko:
À mà bạn biết cách làm thủ công không dùng quy hoạch động post lên luôn nhé.
Thanks.:book:

----------


## gamevui5k

khổ quá , chịu khó nghiên cứu sách LMH đi , có hướng dẫn cụ thể lun . Đọc hỉu thì tự chuyển đc từ kiểu số nguyên wa kiểu kí tự . Sung rụng r` , cũng k thèm nhặt lên , còn bắt ng # nhặt lên bỏ miệng dùm àh. Cố gắng đi . Nếu hết tuần sau , bạn k làm đc mình post code cho nhưng đọc code k hoàn chỉnh vs code hoàn chỉnh cũng thế . K hỉu thì vẫn là k hỉu =.=!

----------


## haqn84

Mình đã biết cách làm thủ công O(n^2) không theo quy hoạc động rồi, cám ơn mấy bạn nhiều.
:emlaugh:

----------


## phukienplus

Quy Hoạch Động là cái gì thế. Cái này mình chưa học ^^!.......

----------


## sccom123

down sách LMH về mà nghiên cứu 
thủ công là ntn ?

----------


## viponline

```
{$B-, Q+, R+} {$M 65500, 0, 655360}
Uses Crt;
Const maxN = 6;
      FI = 'DCC.INP';
      FO = 'DCC.OUT';
Var tu : Array[1..6] Of String;
    tuch : String;
    n, l, max : Byte;
    F : Text;

Procedure KhoiTao;
Var i : Byte;
Begin
        Assign(F, FI);
        Reset(F);
        Readln(F, n);
        l := 255;
        For i := 1 To n Do
        Begin
                Readln(F, tu[i]);
                If l > Length(tu[i]) Then
                Begin
                        l := Length(tu[i]);
                End;
        End;
        Close(F);
        max :=  0;
End;

Procedure Duyet;
Var i, j, k : Byte;
    s : String;
Begin
        For i := 1 To l Do
        For j := 1 To l - i + 1 Do
        If j > max Then
        Begin
                s := Copy(tu[1], i, j);
                k := 2;
                While (k <= n) And (Pos(s, tu[k]) > 0) Do Inc(k);
                If k > n Then
                Begin
                        max := j;
                        tuch := s;
                End;
        End;
End;

Procedure Xuly;
Begin
        Duyet;
        Assign(F, FO);
        Rewrite(F);
        Writeln(F, max);
        Writeln(F, tuch);
        Close(F);
End;

Begin
        KhoiTao;
        Xuly;
End.
```

----------


## seolalen154643

> down sách LMH về mà nghiên cứu 
> thủ công là ntn ?


- Hai dòng for và hàm pos tìm các chuỗi con chung.:book:
- Viết thêm hàm max tính độ dài dài nhất.:book:
[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])* Thân.*
---------------------------------Bài viết đã được trộn ---------------------------------



> ```
> {$B-, Q+, R+} {$M 65500, 0, 655360}
> Uses Crt;
> Const maxN = 6;
>       FI = 'DCC.INP';
>       FO = 'DCC.OUT';
> Var tu : Array[1..6] Of String;
>     tuch : String;
>     n, l, max : Byte;
> ...


_"Begin_
_ KhoiTao;_
_ Xuly;_
_End."_
-> Anh caodai viết thêm thủ tục duyet làm gì thế[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]. Thắc mắc tí:bored:

----------


## tapcuoinet

- trùi , nhìn vào phần xuly đi , có thấy gọi thủ tục duyet k ?
- post code lên tham khảo vs

----------


## mrti

Ơ sorry, mình không thấy, lên độ rồi.
< _Mai mình post, giờ trễ rồi >:emlaugh:_

----------


## demchauau1

> Ơ sorry, mình không thấy, lên độ rồi.
> < _Mai mình post, giờ trễ rồi >:emlaugh:_


Sao không post code lên em! Post lên cho các mem tham khảo nhá!

----------


## nam123

Thời gian không onl nhiều nên mình viết chương trình đơn giản, không file gì hết, mong mấy bạn thông cảm, góp ý để mình cải thiện thuật toán:
uses crt;
var s,s1,s2:string;x:array[1..100] of string;i,j,n,k:integer;
 max:integer;
begin
 readln(s1);
 readln(s2);
 n:=0;
 for j:=1 to length(s1) do
 for i:=1 to length(s1)-j do
 begin
 s:=copy(s1,i,j);
 if pos(s,s2) <> 0 then
 begin
 n:=n+1;
 x[n]:=s;
 end;
 end;
 s:=x[1];
 for k:=2 to n do
 if length(s)<=length(x[k]) then s:=x[k];
 if s='' then write('0') else write(s);
 readln;
end.:emlaugh:

----------


## phamthaovnn

giải thix thuật toán vs [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
-----------------

----------


## bigrat96

bạn binhnguyen ui , code của bạn chỉ tìm đc n~ xâu liên tiếp thôi .Bài này có thể in ra xâu k liên tiếp mà
inp:
abcde
ace
out:
ace

----------


## sangdv

Trời, code này tìm và lưu chuỗi con chung 2 chuỗi s1,s2 vào mảng x. Sau đó tìm max length(x[k]) rồi gán nó vào s.
Trong code, nếu có chuỗi dài hơn, s được gán giá trị mới.
Hiểu không hang_vt[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## hantrongtai1

nhưng mà vs đề này out in ra n~ chuỗi con k liên típ , code bạn chỉ in đc n~ dãy con liên tiếp thôi

----------


## vthao93hp

> nhưng mà vs đề này out in ra n~ chuỗi con k liên típ , code bạn chỉ in đc n~ dãy con liên tiếp thôi


 Bạn ơi, vấn đề của đề bài là in ra xâu con chung liên tục dài nhất. Mình có coi lại bài post đầu topic, xin lỗi về sự thiếu sót của đề bài.
Dù sao cũng cám ơn hangvt nhiều lắm[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------

