#1222. SUBREP - Xâu lặp

Cho là một xâu ký tự, ta gọi xâu lặp bậc của , ký hiệu là xâu tạo thành bằng cách nối liên tiếp xâu đúng lần. Ví dụ “sossossos” là xâu lặp bậc của xâu “sos”.

Định nghĩa xâu là xâu con của xâu nếu ta có thể xóa một vài ký tự của để được xâu . Ví dụ xâu “gotwin” là xâu con của xâu “gonewiththewind”.

Yêu cầu: Cho hai xâu và . Hãy tìm xâu lặp bậc lớn nhất của là xâu con của xâu , cho biết bậc đó.

Dữ liệu vào:

• Dòng đầu chứa xâu chỉ gồm các chữ cái thường độ dài không quá ;
• Dòng thứ hai chứa xâu chỉ gồm các chữ cái thường độ dài không quá .

Dữ liệu ra:

• Ghi ra số lớn nhất mà là xâu con của xâu .

Ví dụ

Dữ liệu vào:

pet
hopeforthebestbutpreparefortheworst

Dữ liệu ra:

2