Chuỗi Chung Dài Nhất · canuc80k1206

Cho hai chuỗi $s$ và $t$ . Một dãy con của một chuỗi được tạo bằng cách xóa đi không hoặc nhiều ký tự nhưng giữ nguyên thứ tự các ký tự còn lại. Hãy in ra một dãy con chung có độ dài lớn nhất của $s$ và $t$ . Nếu có nhiều đáp án, được in bất kỳ đáp án nào; nếu độ dài lớn nhất bằng $0$ , in một dòng rỗng.

Input

Dòng thứ nhất chứa chuỗi $s$ .
Dòng thứ hai chứa chuỗi $t$ .

Output

In một dãy con chung dài nhất của $s$ và $t$ . Nếu có nhiều đáp án, in một đáp án bất kỳ.

Constraints

$1 \leq ∣ s ∣, ∣ t ∣ \leq 3000$ .
Hai chuỗi chỉ gồm các chữ cái thường tiếng Anh.

Scoring

Subtask $1$ ( $50%$ số điểm): $∣ s ∣, ∣ t ∣ \leq 18$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

abcde
ace

Output

ace

Giải thích: Xóa $b$ và $d$ khỏi chuỗi abcde thu được ace, đồng thời đây chính là chuỗi thứ hai. Vì chuỗi thứ hai chỉ dài $3$ , không thể có dãy con chung dài hơn.

Ý tưởng: Đặt dp[i][j] là độ dài dãy con chung dài nhất của s[0..i-1] và t[0..j-1]. Nếu hai ký tự cuối bằng nhau, dùng cặp ký tự ấy: dp[i][j]=dp[i-1][j-1]+1. Nếu khác nhau, bỏ một trong hai ký tự cuối: dp[i][j]=max(dp[i-1][j],dp[i][j-1]). Sau khi tính bảng, đi ngược từ (n,m) để dựng đáp án.
Chứng minh tính đúng đắn: Nếu hai ký tự cuối bằng nhau, có một phương án tối ưu kết thúc bằng ký tự đó; bỏ ký tự cuối khỏi hai chuỗi và khỏi đáp án để nhận bài toán trên hai tiền tố. Nếu chúng khác nhau, một dãy con chung không thể đồng thời dùng cả hai ký tự cuối, nên ít nhất một ký tự bị bỏ và đáp án nằm trong một trong hai trạng thái kề. Công thức xét đủ các trường hợp. Khi truy vết, mỗi ký tự được thêm chỉ khi hai ký tự hiện tại bằng nhau, còn các bước khác giữ nguyên giá trị DP; do đó chuỗi dựng được là dãy con chung và có đúng độ dài tối ưu.
Độ phức tạp: Thời gian O(|s|·|t|) và bộ nhớ O(|s|·|t|).