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

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

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

Dữ liệu vào:

+ Dòng 1 chứa xâu \(S\) chỉ gồm các chữ cái thường độ dài không quá \(10^{6}\).

+ Dòng 2 chứa xâu \(T\) chỉ gồm các chữ cái thường độ dài không quá \(10^{6}\).

Kết quả:

+ Ghi \(k\) lớn nhất mà \(S^{k}\) là xâu con của xâu \(T\)