Xâu con chung dài nhất 4

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Thời gian:
Pascal 3.0s
Bộ nhớ:
Pascal 20M
Tác giả:
hhoangcpascal
Dạng bài
Điểm: 400 (p) Thời gian: 0.75s 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

  • Gồm hai dòng
  • Dòng thứ nhất chứa xâu \(S\).
  • Dòng thứ hai chứa xâu \(T\).

Output

  • In ra xâu con chung dài nhất của hai xâu \(S\) và \(T\). Nếu có nhiều xâu con dài nhất thoả mãn, in ra một xâu 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.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(|S|, |T| \le 10^3\).
  • Subtask \(2\) (\(50\%\) số điểm): \(|S|, |T| \le 10^4\).

Example

Test 1

Input 
axyb
abyxb
Output 
axb

Bình luận