Cho một xâu kí tự , một xâu được gọi là xâu con của xâu nếu như nó có thể được tạo thành bằng cách xoá đi một vài kí tự của xâu và giữ nguyên thứ tự các kí tự còn lại. Ví dụ: ant là một xâu con của xâu talent.
Cho hai xâu . Ta định nghĩa là độ dài của xâu ngắn nhất là xâu con của nhưng không phải xâu con của . Nếu không tồn tại xâu nào như thế thì .
Ví dụ: vì:
Mọi xâu con độ dài không vượt quá của xyzt đều là một xâu con của yztxx;
Xâu con xt của xyzt có độ dài và không phải là xâu con của yztxx.
Cho một số nguyên dương . Chúng ta chỉ quan tâm đến những xâu có độ dài với kí tự và kí tự . Trong những xâu như thế hãy tìm ra xâu và sao cho đạt giá trị lớn nhất.
Dữ liệu vào:
Chứa duy nhất một số nguyên dương .
Dữ liệu ra:
Dòng thứ nhất ứng với xâu ;
Dòng thứ hai ứng với xâu .
Nếu có nhiều cặp thỏa mãn (tối ưu), in ra bất cứ cặp nào.
Ví dụ:
Dữ liệu vào:
1
Dữ liệu ra:
01
Giải thích:
Nhận thấy hai xâu 10 và 01 có vì mọi xâu con khác 10 của 10 đều là xâu con của 01.