Bedao Regular Contest 11 - ABSTRING
View as PDFHương hoa bay nhẹ nhàng qua kẽ lá.
Lời thì thầm của đá khẽ qua tai.
Không cần giới thiệu chắc hẳn bạn cũng không biết 2 câu thơ trên là của ai. Nhưng theo mình biết, thì 2 câu thơ đó chính là châm ngôn sống của Lành - 1 người đàn ông mạnh mẽ nhưng sống rất nội tâm. Hằng ngày khi không có việc gì làm, Lành thường có những biểu hiện như tay nhặt lá, chân đá ống bơ (đúng như châm ngôn sống của mình). Những lúc khác thì Lành lại tự nghĩ ra những câu đố hóc búa, thách thức chính bản thân mình cũng như mọi người. Hôm nay cũng như vậy, Lành đã nghĩ ra bài toán như sau:
- Cho một xâu kí tự chỉ chứa ~2~ kí tự '~a~' và '~b~', hãy ~1~ tìm xâu con liên tiếp sao cho tần suất xuất hiện là lớn nhất.
- Tần suất xuất hiện là số lần xâu con liên tiếp '~aba~' xuất hiện / độ dài.
Tuy nhiên các xâu kí tự thì có vẻ rất dài, vì vậy các bạn lập trình viên của ~Bedao \ Contest~ hãy giúp đỡ Lành nhé.
Input
- Dòng đầu tiên nhập số nguyên dương ~n \ (3 \le n \le 10^6)~ là độ dài của xâu kí tự.
- Dòng thứ 2 nhập xâu kí tự có độ dài ~n~ chỉ chứa ~2~ kí tự '~a~' và '~b~' (Dữ liệu đảm bảo có ít nhất 1 xâu '~aba~').
Output
- In ra 1 dòng duy nhất chứa xâu kí tự cần tìm. Nếu có nhiều xâu con có tần suất xuất hiện của xâu '~aba~' là lớn nhất thì in ra xâu có thứ tự từ điển nhỏ nhất.
Subtask
- ~20\%~ số test có ~n \le 10^2~.
- ~30\%~ số test có ~n \le 10^3~.
- Còn lại không có điều kiện gì thêm.
Sample Input
8
abaababa
Sample Output
ababa
Note
Ta thấy xâu '~ababa~' có tần suất xuất hiện là ~2/5~ là lớn nhất, còn xâu '~abaababa~' có tần suất xuất hiện là ~3/8~ bé hơn ~2/5~.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
Thiếu sự chú ý thì cũng đừng có xả rác lên đây. Bẩn lắm.