chuỗi con lớn nhất

[anhduynguyen]

mình đã dò thử nhưng không biết sai chỗ nào strncpy or for. các bạn xem giúp

#include <stdio.h>
#include <conio.h>
#include <string.h>

char * nhap(char * &s){
	printf("nhap chuoi: ");
	gets(s);
	return s;
}

void main(){
	clrscr();
	printf("xet chuoi con lon I of s1 va s2,leng s1>leng s2");
	char *s1,*s2,*s3,*s4,*s5;
	nhap(s1);
	nhap(s2);
	s4="";
	for(int i=0;i<strlen(s2)-1;i++)
	{
		strcpy(s3,s2+i);
		int j=strlen(s3);
		while (j>0)
		{	strncpy(s4,s3,j);
			j--;
			if (strstr(s1,s4)!=NULL)
				if (strlen(s5)<strlen(s4))
					s5=s4;
		}
	}
	printf("chuoi con lon nhat la %s",s5);
	getch();
}

[benvang999]

bạn có thể nói rõ ý bạn muốn được không
cho một vài ví dụ nữa chứ mình chưa hiểu ý của chương trình lắm

[rox_rook]

Bạn có thể giải thích chuỗi con lớn nhất là chuỗi con thế nào trong 2 chuỗi không? Bạn có thể cho 1 ví dụ không? Mình đọc code mà chẳng hiểu bạn đang làm gì nữa thì làm sao giúp bạn được :(?

[anhduynguyen]

Xin lỗi nhé, mình quên
Chương trình yêu cầu nhập 2 chuỗi s1 và s2, s1>s2
tìm chuỗi con nhỏ nhất
Ví dụ nhé:
s1= abcdefg
s2=kbcdl
=> chuỗi con lớn nhất là bcd
Các bạn check lại giùm mình nhé. Không biết sai chỗ nào. Thanks

[rox_rook]

Xin lỗi nhé, mình quên
Chương trình yêu cầu nhập 2 chuỗi s1 và s2, s1>s2
tìm chuỗi con nhỏ nhất
Ví dụ nhé:
s1= abcdefg
s2=kbcdl
=> chuỗi con lớn nhất là bcd

Hic, mình sợ bạn luôn !!!
Mà chuỗi con được định nghĩa thế nào là lớn nhất ? ( hoặc nhỏ nhất )
Là chuỗi con lớn hơn cả 2 chuỗi trên hay....?
Hay là chuỗi con chung ?

s1>s2

DK này có là sao nhỉ ? Trong khi trong code bạn lại ghi :

printf("xet chuoi con lon I of s1 va s2,leng s1>leng s2");

!!!!!!
Nếu ví dụ như trên thì mình nói vậy được không ?
abc > bcd ?
Sorry mình hơi chậm hiểu, nhưng bạn ghi ra rõ 1 tí được không ?

[anhduynguyen]

chuỗi con là chuỗi chung của cả 2 chuổi s1 và s2, mình viết tắt s2<s1 thực ra chiều dài chuỗi s2< chiều dài chuỗi s1. Còn dòng đó chỉ là nhắc lại đề thôi không liên quan đến bài toán.
bạn không thể nói abc>bcd vì abc không là chuỗi con của s1 và s2. Nếu nói chuỗi con thì còn nhiều chuỗi con khác trong ví dụ trên như bc, cd, b, c. nhưng chuỗi con lớn nhất là bcd/

[anhduynguyen]

xin nói thêm. Mình đã dùng watch để dò lỗi thử và thấy là hàm

strncpy(s4,s3,j);

thực hiện không đúng dù j vẫn lặp chính xác. Cũng có thể là do lỗi vùng nhớ mà mình không xác định được.
Mình cho chạy bộ thử
s1=abcdef
s2=mbcdk
thì kết quả ra dk hoặc kí tự đặc biệt.

[rox_rook]

Ý tưởng của bạn thì mình có đọc sơ qua nhưng hình như thấy vẫn chưa đủ ! Bài này nếu đúng phải là tìm chuỗi con chung dài nhất của 2 chuỗi thì có lẽ đúng hơn . Và ý tưởng của nó sẽ là dùng Quy Hoạch Đông. Và nếu tìm được dãy con chung rồi thì việc tìm dãy con lớn nhất trong dãy đó là mình nghĩ có thể thực hiện được ! Bạn suy nghĩ về ý tưởng nào thử xem. Mình sẽ làm thử xem sao ! Thân !

[anhduynguyen]

ờ đây mình dùng vét cạn. Đúng như bạn nói chính xác đây là chương trình tìm chuỗi con dài nhất. Mình đã thử thay đổi một số chi tiết trong chương trình nhưng vẫn chưa đạt được mục đích. Mong câu trả lời. Thanks

[rox_rook]

Bài này nếu giải bằng Quy Hoạch Động thì như sau :
Gọi Grid[i][j] là dãy độ dài dãy con chung dài nhất của 2 dãy X[] và Y[], công thức truy hồi đơn giản như sau :

if ( X[i] == Y[j] )
{
Grid[i][j] = Grid[i-1][j-1] + 1;
}
else
{
Grid[i][j] = GetMax(Grid[i][j-1], Grid[i-1][j]);
}

#include <iostream>
#include <string>
#include <algorithm> //swap function

using namespace std;

const int size = 100;

char X_string[size], 
     Y_string[size],
     Y[size],
     X[size],
     subString[size];
     
int Grid[size][size]; // Matrix Solution
int xL, yL; // X length and Y length

int GetMax(int a, int b)
{
    int tmp;
    if ( a > b ) tmp = a;
    else         tmp = b;
      
    return tmp;
}

void Initialization()
{
    for ( int i = 0; i <= xL; i++)
    {
        Grid[i][0] = 0;
    }
    for ( int j = 0; j <= yL; j++)
    {
        Grid[0][j] = 0;
    }
    X[0] = ' ';
    Y[0] = ' ';
    for ( int i = 1; i <= xL; i++)
    {
        X[i] = X_string[i-1];
    }
    for ( int i = 1; i <= yL; i++)
    {
        Y[i] = Y_string[i-1];
    }
}

void DynamicProgramming()
{
    for (int i = 1; i <= xL; i++)
    {
        for (int j = 1; j <= yL; j++)
        {
            if ( X[i] == Y[j] )
            {
                Grid[i][j] = Grid[i-1][j-1] + 1;
            }
            else
            {
                Grid[i][j] = GetMax(Grid[i][j-1], Grid[i-1][j]);
            }
        }
    }
}

void TraceString()
{
    int xO = xL,
        yO = yL;
    
    int position = 0;
        
    do
    {
        if ( X[xO] == Y[yO] )
        {
            position++;
            subString[position] = X[xO];
            xO--; 
            yO--;
        }
        else
        {      
            if ( Grid[xO][yO] == Grid[xO][yO-1] ) yO--;
            else                                  xO--;
        }
    }
    while ( xO > 0 && yO > 0 );
    
    for (int i = 1; i <= position/2; i++)
    {
        swap(subString[i], subString[position-i+1]);
    }
}
void PrintString()
{
    cout << "\n------------------------\n";
    cout << "\nThe maximum length is : \n" << Grid[xL][yL];
    cout << "\n\n";
    cout << "Longest common substring is : " << endl;
    for ( int i = 0; i <= Grid[xL][yL]; i++)
    {
        cout << subString[i];
    }
    
}    
int main()
{
    cout << "Enter 1-st String : " << endl;
    cin >> X_string;
    cout << "Enter 2-nd String : " << endl;
    cin >> Y_string;
    
    xL = strlen(X_string);
    yL = strlen(Y_string);

   
    Initialization();
    DynamicProgramming();
    TraceString();
    PrintString();
    
    return 0;
} 

Nếu bạn có chỗ nào không hiểu thì mình sẽ giải thích ! Thân !