Xoay vòng xâu nhỏ nhất
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Đề bài
Cho một xâu $S$ có độ dài $N$ chỉ gồm các chữ cái tiếng Anh thường. Một phép xoay vòng $k$ bước ($0 \le k < N$) biến $S$ thành $S[k..N-1] + S[0..k-1]$. Hãy tìm xâu xoay vòng có thứ tự từ điển nhỏ nhất và chỉ số $k$ nhỏ nhất tạo ra xâu đó.
Dữ liệu vào
Một dòng duy nhất chứa xâu $S$.
Dữ liệu ra
- Dòng đầu tiên ghi chỉ số $k$ nhỏ nhất ($0 \le k < N$).
- Dòng thứ hai ghi xâu xoay vòng nhỏ nhất tìm được.
Ví dụ
| Input | Output |
|---|---|
| alabala | 6 aalabal |
| baab | 1 aabb |
Giới hạn
$1 \le |S| \le 5 \cdot 10^5$.
Community Discussion