Nhận xét: Thứ tự từ điển phụ thuộc vào số lượng xâu xoay có thứ tự từ điển nhỏ hơn với xâu ban đầu.

Subtask 1, 2, 3

Vì giới hạn ~|s|~ nhỏ nên ta có thể áp dụng độ phức tạp ~O(n)~ để so sánh xâu khởi đầu với một xâu xoay.

Độ phức tạp: ~O(n^2)~.

Subtask 4, 5

Giới hạn ~|s|~ lớn làm ta không thể so sánh xâu bằng cách cũ được. Ta có thể áp dụng hash kết hợp với chặt nhị phân. Các bạn có thể đọc tài liệu hash tại đây.

Vậy làm sao để ta có thể chặt nhị phân trong tình huống này? Ta nhận thấy hash có thể so sánh hai xâu có bằng nhau hay không. Hay nói cách khác, giả sử ta so sánh hai xâu ~a~ và ~b~ có cùng độ dài ~n~, gọi mảng ~c~ là mảng so sánh. Trong đó ~c_i = 1~ khi xâu con đoạn ~[1; i]~ của xâu ~a~ bằng xâu con đoạn ~[1; i]~ của xâu ~b~ và ~c_i = 0~ trong trường hợp ngược lại.

Nhận xét: Dãy ~c~ nhận được sẽ là ~1~ dãy giảm dần. Vì vậy ta có thể áp dụng chặt nhị phân để tìm vị trí ~i~ lớn nhất sao cho ~c_i = 1~.

Để so sánh hai xâu sau khi tìm được ~i~, ta so sánh tới ký tự ~i + 1~ của cả hai xâu. Trường hợp ~i = n~ thì hai xâu bằng nhau.

Độ phức tạp: ~O(n \times \log{n})~.