Dãy con chung dài nhất

[G.Perelman]

Chào các bạn mình có 1 vấn đề mong mọi người giải đáp giúp:
"Cho 2 xâu X=<X1X2....Xm> và xâu Y=<Y1Y2....Yn> .1 dãy con chung của X và Y là xâu có được bằng cách xoá bớt 1 số phần tử của X và của Y,
Yêu cầu liệt kê ra tất cả các dãy con chung dài nhất.
Vấn đề tìm độ dài xâu con chung dài nhất thì mình đã giải quyết xong bằng thuật toán quy hoạch động(cái này có nhiều trong các sách về thuật toán) ,nhưng mình gặp khúc mắc ở chỗ in ra mọi dãy con chung lớn nhất của bài toán có nhiều đáp án

vd :X=”a45y7i9”
Y=”y475f90A!” thì dáp án là 459 và y79

Cho mình hỏi thêm các bạn có địa chỉ nào có thể giúp mình down những bộ file test(bao gồm cả input và output) cho những bài toán phổ biến trong tin học như “đường đi ngắn nhất trong đồ thị",”knapsack”,”bài toán người du lịch” ,”bài toán cây khung”,”dãy con tăng dài nhất”,”giao và hợp của n đoạn cho trước”...
ý mình là cần những test rất lớn để kiểm tra tính đúng đắn của những thuật toán mình đã cài.

Rất mong nhận được hồi âm của các bạn.

[fedo]

Chào các bạn mình có 1 vấn đề mong mọi người giải đáp giúp:
"Cho 2 xâu X=<X1X2....Xm> và xâu Y=<Y1Y2....Yn> .1 dãy con chung của X và Y là xâu có được bằng cách xoá bớt 1 số phần tử của X và của Y,
vd :X=”a45y7i9”
Y=”y475f90A!” thì dáp án là 459 và y79

Chào bạn, mình chưa hiểu tại sao đáp án là 459 và y79 được không(hic, mình hơi chuối). Bạn có thể nói rõ thêm về dãy con chung được không. Định nghĩa và ví dụ của bạn hơi khó hiểu. Sao đáp án lại không là 45y79 nhỉ.
Ý quên mới search lại trên forum có một topic nói về cái này nè
http://forums.congdongcviet.com/arch...hp/t-4277.html
Have fun!

[G.Perelman]

Dãy con của 1 dãy thì yêu cầu thứ tự các phần tử phải giữ nguyên ,trong ví dụ của mình do kí tự "y" đứng trước kí tự "5" nên đáp án của bạn không được.
cái định nghĩa của mình đưa ra là khá chuẩn do mình theo các sách rồi đấy.
nhưng trong sách họ chưa giải quyết được vấn đề là "liệt kê mọi dãy con chung dài nhất".cái topic của bạn "rox_rook" đã đưa ra giải thuật đúng nhưng vẫn chưa giải quyết được vấn đề trên,vả lại mình cũng chưa ngâm cứu về C++ cho nên code của rox_rook mình không hiểu cho lắm nhưng về tư tưởng là đúng rồi.