Tèo có hai xâu \(A\) và \(B\). Tèo muốn tìm xâu con chung dài nhất của hai xâu (Longest Common Substring). Xâu con chung là xâu xuất hiện ở cả hai xâu. Hãy dùng hash kết hợp tìm kiếm nhị phân để giải bài toán.

Định dạng đầu vào

• Dòng đầu chứa xâu \(A\).
• Dòng thứ hai chứa xâu \(B\).
• Độ dài mỗi xâu không quá \(5000\). Các xâu chỉ gồm chữ cái in thường.

Định dạng đầu ra

• In ra độ dài xâu con chung dài nhất.

Ví dụ

Input:

abcdef
bcdfg

Output:

4

Giải thích: Xâu bcdf xuất hiện ở cả hai xâu.

Ràng buộc

• 50% số điểm: \(|A|, |B| \le 500\).
• 50% số điểm còn lại: \(|A|, |B| \le 5000\).