Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng tiếp cận
Bài toán cổ điển: tìm xoay vòng nhỏ nhất từ điển trong .
Nhận xét quan trọng
- Có xoay vòng; so sánh đôi một mỗi cặp tốn tới ký tự, dẫn tới — không khả thi khi .
- Nối . Khi đó mọi xoay vòng của chính là một xâu con liên tiếp độ dài của .
Thuật toán
Thuật toán Booth (Least Rotation) — :
T = S + S, f[0..2N-1] = -1, k = 0
for j in 1 .. 2N-1:
i = f[j - k - 1]
while i != -1 and T[j] != T[k + i + 1]:
if T[j] < T[k + i + 1]: k = j - i - 1
i = f[i]
if T[j] != T[k + i + 1]:
if T[j] < T[k + i + 1]: k = j
f[j - k] = -1
else:
f[j - k] = i + 1
return k
Đáp án: .
Độ phức tạp
- Thời gian:
- Bộ nhớ:
https://oj.chuyentin.pro/problem/lexrot/editorial
Bình luận