Secret Password

Minh có một ví điện tử đã lâu không sử dụng chứa hơn 100000 bitcoin trong đó, giá bitcoin tăng cao khiến Minh mừng rỡ không thôi, Minh muốn bán số bitcoin trong ví đi nhưng lại quên mất mật khẩu của ví điện tử.

Cũng may là Minh đã đề phòng trường hợp này nên lúc trước anh đã tạo ra hai chuỗi ký tự key1 và key2, mật khẩu để mở ra chiếc ví kia chính là độ dài của chuỗi con chung lớn nhất. Hãy giúp Minh tìm lại “chìa khóa” mở ra kho báu khổng lồ kia nhé.

Nếu không có chuỗi con nào thì mật khẩu sẽ là 6008009.

Ví dụ:

• Với key1 = "ABAB" và key2 = "BABA" thì getThePassword(key1, key2) = 3.
• Với key1 = "KoXvx" và key2 = "sbrKfwkr" thì getThePassword(key1, key2) = 1.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.
• [Đầu vào] String key1, String key2
1 ≤ key1.length() ≤ 1000.
  1 ≤ key2.length() ≤ 1000. 
• [Đầu ra] Integer