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.
-
1
vinhntndu
2:06 p.m. 7 Tháng 8, 2020
-
1
cuom1999
9:32 p.m. 7 Tháng 8, 2020
-
1
vinhntndu
10:51 p.m. 7 Tháng 8, 2020
-
1
dangquan6b
7:38 p.m. 7 Tháng 8, 2020
-
1
dangquan6b
7:24 p.m. 7 Tháng 8, 2020
-
1
vinhntndu
7:38 p.m. 7 Tháng 8, 2020
1 bình luận nữadạ em chưa sinh test 1000 được ạ, với lại in theo thứ tự nên chỉ có 1 th ạ
Ah ý anh là số LCS chung là nhiều ấy.
VD S1=aaabb S2=aab thì in aab 4 lần ấy anh
Nhỡ em cho A = aaa...bbb...ccc...ddd...eee... mỗi chữ có 20 lần xuất hiện
B = aabbccddee
Thì sẽ có đâu đó 190^5 cách chọn, in ra thốn lắm anh 🙂
Ơ, có 1 TH là sao ạ :V
1 trường hợp theo thứ tự