Bài 1. So sánh hai xâu văn bản

Mô tả

Cho hai xâu A và B chỉ gồm chữ cái tiếng Anh thường.
Hãy tìm độ dài của dãy con chung dài nhất (Longest Common Subsequence - LCS) của hai xâu đó.

Một dãy con được tạo ra bằng cách xóa đi một số ký tự bất kỳ nhưng giữ nguyên thứ tự tương đối của các ký tự còn lại.

Input

• Dòng 1 chứa xâu A.
• Dòng 2 chứa xâu B.

Output

• In ra một số nguyên là độ dài LCS của A và B.

Ràng buộc

• 1 <= |A|, |B| <= 1000

Subtask

• Subtask 1 (30%): |A|, |B| <= 100
• Subtask 2 (70%): Không có ràng buộc gì thêm.

Ví dụ

Input

abcbdab
bdcaba

Output

4

Giải thích ví dụ

Một LCS có thể là bcba hoặc bdab, nên đáp án bằng 4.