Xâu đầu cuối
View as PDF
Cho một xâu ~S~ có độ dài ~n \le 5*10^5~ gồm các chữ cái tiếng Anh in thường.
Một xâu tiền tố của xâu ~S~ được gọi là đẹp nếu nó bằng với xâu hậu tố tương ứng với nó. Hay nói cách khác, tiền tố độ dài ~L~ có dạng ~S[1,2,...,L]~ phải bằng với hậu tố độ dài ~L~ có dạng ~S[n-L+1,n-L+2,...,n]~.
Do việc tìm tất cả các xâu tiền tố đẹp là một công việc khá dễ dàng, nên Tí muốn giao thêm cho các bạn một công việc nữa, đó là với mỗi xâu tiền tố đẹp, hãy đếm xem có bao nhiêu xâu con liên tiếp trong ~S~ bằng với tiền tố đó.
Input
Dòng đầu gồm số nguyên dương ~n~ (~n \le 5*10^5~) miêu tả độ dài của xâu ~S~.
Dòng thứ hai miêu tả xâu ~S~.
Output
Dòng đầu tiên in ra số nguyên dương ~m~ là số lượng xâu tiền tố đẹp.
~m~ dòng sau, mỗi dòng in ra hai số nguyên dương ~u_i~ ~v_i~, với ~u_i~ là độ dài của xâu tiền tố đẹp tìm được, và ~v_i~ là số lần xuất hiện của nó.
Hãy in ra các cặp ~u_i~ ~v_i~ theo thứ tự tăng dần của ~u_i~.
Sample Input 1
7
abacaba
Sample Output 1
3
1 4
3 2
7 1
Sample Input 2
4
aaaa
Sample Output 2
4
1 4
2 3
3 2
4 1
Comments
This comment is hidden due to too much negative feedback. Show it anyway.