trang chủ / đề bài / lexrot / lời giải

Xoay vòng nhỏ nhất từ điển

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.
Tác giả: huunguyenhuunguyen

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 O(N).

Nhận xét quan trọng

  • Có N xoay vòng; so sánh đôi một mỗi cặp tốn tới O(N) ký tự, dẫn tới O(N2) — không khả thi khi N=106.
  • Nối T=S+S. Khi đó mọi xoay vòng của S chính là một xâu con liên tiếp độ dài N của T.

Thuật toán

Thuật toán Booth (Least Rotation) — O(N):

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: S[k..N−1]+S[0..k−1].

Độ phức tạp

  • Thời gian: O(N)
  • Bộ nhớ: O(N)

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0