All LCS
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Có lẽ ai cũng đã biết bài toán LONGEST COMMON SUBSEQUENCE. Vậy hôm nay có một bài toán khó hơn: In tất cả các xâu con chung dài nhất của hai xâu cho trước.
Input
- Gồm hai dòng là hai xâu \(A\) và \(B\). \((1 \leq |A|, |B| \leq 100)\).
Output
- Gồm nhiều dòng, mỗi dòng là một xâu con chung dài nhất của hai xâu \(A\) và \(B\) theo thứ tự từ điển.
Example
Test 1
Input
baadefg
aabedf Output
aadf
aaef
Bình luận
vinhntndu. Test hơi nhỏ thì phải. Và có trường hợp có thể có rất nhiều đáp án.
Cho mình hỏi là in ra tất cả xâu con chung dài nhất, hay chỉ là những xâu con chung dài nhất phân biệt?
Ví dụ :
aaaa
aaaaba