Chọn Đội tuyển HSGQG Quảng Trị 2024 - PADBLE
Xem dạng PDF
Việt Anh định nghĩa xâu đối xứng đôi PADBLE là xâu gồm các kí tự in thường ~'a..z'~ trong bảng mã ASCII có độ dài chẵn được ghép thành từ hai xâu con đối xứng có độ dài bằng nhau và có ít nhất hai kí tự khác nhau. Ví dụ xâu ~abacdc~, ~ab~, ~aabb~ là các xâu đối xứng đôi, nhưng xâu ~aaaaabbb~ không phải là xâu đối xứng đôi.
Yêu cầu: Cho xâu ~S~ chỉ chứa các kí tự '~a~' và '~b~', em hãy lập trình giúp Việt Anh tìm độ dài xâu PADBLE lớn nhất và có bao nhiêu xâu con có cùng độ dài lớn nhất đó trong xâu ~S~?
Input
Vào từ tệp văn bản PADBLE.INP chứa xâu ~S~ gồm các kí tự ~a~ và ~b~.
Output
Ghi ra tệp văn bản PADBLE.OUT gồm hai số nguyên là độ dài xâu đối xứng đôi lớn nhất và số xâu có độ dài lớn nhất cách nhau dấu cách. Nếu không có xâu nào thỏa mãn thì in ra ~-1~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~40~ | ~| S | \leq 10^2~ |
| 2 | ~30~ | ~| S | \leq 10^3~ |
| 3 | ~30~ | ~| S | \leq 10^5~ |
Sample Input 1
aaabbaabbbaa
Sample Output 1
4 4
Sample Input 2
aaabbaabbbaaaa
Sample Output 2
6 1
Sample Input 3
aaaaaaaaaaa
Sample Output 3
-1
Notes
Trong ví dụ ~1~, xâu đối xứng đôi độ dài lớn nhất là ~4~ và có ~4~ xâu con thỏa mãn xâu PADBLE là ~aabb~ bắt đầu vị trí số ~2~, ~bbaa~ bắt đầu vị trí số ~4~, ~aabb~ bắt đầu vị trí số ~6~, ~bbaa~ bắt đầu vị trí số ~9~.
Bình luận
trâu cũng ac