Xâu con chung dài nhất

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
jumptozero
Dạng bài
Điểm: 400 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho hai xâu \(s\) và \(t\) chỉ gồm các chữ cái thường \('a'..'z'\). Tìm xâu con chung dài nhất (subsequence) của hai xâu \(s\) và \(t\)

Input

  • Dòng thứ nhất chứa xâu \(s(1\le |s|\le 3000)\)

  • Dòng thứ hai chứa xâu \(t(1\le |t|\le 3000)\)

Output

  • In ra xâu chung dài nhất cần tìm. Nếu có nhiều đáp án in ra bất kì !

Chú ý: Một xâu con của một xâu \(x\) bất kì thu được bằng cách xóa đi một vài kí tự (có thể không xóa kí tự nào) từ xâu \(x\) và nối những phần tử còn lại mà không thay đổi thứ tự của chúng.

Example

Test 1

Input 
axyb
abyxb
Output 
axb
Note

Giải thích: Ở đây có hai đáp \(axb\) và \(ayb\) đều thỏa mãn nên ta có thể in ra một cái bất kì , trong trường hợp này nó là \(axb\)

Bình luận


  • 0
    DucAnhkg    12:20 p.m. 25 Tháng 2, 2024

    xin test 2 được không ạ
    mình thấy chỉ có 1 hàng


    • -30
      nguyenduy123    8:40 a.m. 31 Tháng 12, 2022

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

      2 phản hồi

      • 2
        mcsmuscle    11:31 a.m. 4 Tháng 10, 2021

        e sài python mà thời gian ngắn quá, có cách nào chỉnh đc không ạ