All LCS

Xem PDF



Tác giả:
Dạng bài
Đ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\)\(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\)\(B\) theo thứ tự từ điển.

Example

Test 1

Input
baadefg
aabedf 
Output
aadf
aaef

Bình luận


  • 1
    letangphuquy    6:14 p.m. 5 Tháng 8, 2020

    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

    • 4 chữ a đầu tiên (1 cách)
    • 1 chữ a ở cuối và tổ hợp chập 3 của 4 chữ a đầu (= 4C3 = 4) cách
    • Tổng cộng là 5 cách

    • 0
      vinhntndu    6:23 p.m. 5 Tháng 8, 2020

      ý 1


      • 0
        letangphuquy    6:25 p.m. 5 Tháng 8, 2020

        vâng ạ, nếu là tất cả thì nhìn vào có thể có hướng làm ngay :v


        • 0
          vinhntndu    7:31 p.m. 5 Tháng 8, 2020

          phân biệt thì thêm 1 vector nữa là đc, hoặc 1 biến ktra

      1 bình luận nữa