Bài. Chuỗi ADN chung dài nhất

Mô tả

Hai chuỗi ADN chỉ gồm các ký tự A, C, G, T.
Hãy tìm độ dài dãy con chung dài nhất của hai chuỗi ADN này.

Input

• Dòng 1 chứa chuỗi ADN thứ nhất.
• Dòng 2 chứa chuỗi ADN thứ hai.

Output

• In ra độ dài LCS của hai chuỗi.

Ràng buộc

• 1 <= độ dài mỗi chuỗi <= 3000

Subtask

• Subtask 1 (25%): độ dài mỗi chuỗi không quá 300
• Subtask 2 (75%): Không có ràng buộc gì thêm.

Ví dụ

Input

ACGTAC
CATGCA

Output

4

Giải thích ví dụ

Một LCS có thể là ATAC hoặc CGTA.