Jill và Jane là hai chị em. Giáng sinh năm ngoái, mỗi người được tặng một sợi dây gồm những hạt nhiều màu. Ta có thể biểu diễn mỗi màu bằng một chữ cái trong bảng chữ cái tiếng Anh, từ a đến z, và mỗi sợi dây hạt bằng một xâu.

Hai chị em muốn làm vòng cổ từ những sợi dây của mình. Để làm một chiếc vòng cổ, mỗi người có thể bỏ đi một số hạt ở hai đầu dây (có thể không bỏ hạt nào), rồi nối hai đầu của phần dây còn lại. Chiếc vòng cổ thu được có thể được xoay và lật lại.

Hai chị em muốn những chiếc vòng cổ trông giống hệt nhau và dài nhất có thể. Độ dài lớn nhất mà họ có thể đạt được là bao nhiêu?

Dữ liệu vào

Dòng thứ nhất và dòng thứ hai, mỗi dòng chứa một xâu không rỗng gồm không quá \(N\) chữ cái thường, lần lượt mô tả sợi dây hạt của Jill và Jane.

Dữ liệu ra

Dòng đầu tiên chứa một số nguyên dương duy nhất: số hạt lớn nhất mà mỗi chiếc vòng cổ có thể có. Dữ liệu bảo đảm có thể tạo được hai chiếc vòng cổ có độ dài dương.

Dòng thứ hai chứa hai số nguyên: vị trí bắt đầu của phần dây được chọn làm vòng cổ trong xâu của Jill và trong xâu của Jane, theo thứ tự đó. Nếu có nhiều cách chọn, in bất kỳ cách nào. Các vị trí được đánh số từ trái sang phải, bắt đầu từ \(0\).

Ràng buộc

Mỗi xâu có độ dài từ \(1\) đến \(N\), với \(N\le 3000\), và chỉ gồm các chữ cái thường từ a đến z.

Bài này chỉ hỗ trợ C++17; giới hạn \(3\) MB của nhóm \(4\) được trình chấm áp dụng trực tiếp.

Phân nhóm

Chương trình nhận toàn bộ số điểm của một nhóm nếu tìm đúng những chiếc vòng cổ dài nhất có thể trong mọi test của nhóm. Nếu trong mỗi test của nhóm, chương trình tìm được những chiếc vòng cổ có độ dài ít nhất bằng một nửa độ dài tối ưu, chương trình nhận được \(20\%\) số điểm của nhóm.

1. Nhóm 1 (25 điểm): mỗi xâu không rỗng có độ dài không quá \(N=100\).
2. Nhóm 2 (20 điểm): mỗi xâu không rỗng có độ dài không quá \(N=400\).
3. Nhóm 3 (40 điểm): mỗi xâu không rỗng có độ dài không quá \(N=3000\).
4. Nhóm 4 (15 điểm): mỗi xâu không rỗng có độ dài không quá \(N=3000\); giới hạn thời gian không đổi, nhưng chương trình chỉ được sử dụng \(3\) MB bộ nhớ.

Ví dụ

zxyabcd
yxbadctz

4
3 2

Nguồn

Baltic Olympiad in Informatics 2019, ngày 2, Tartu, Estonia, 27/4–2/5/2019. Giấy phép CC BY-SA 4.0.