Booth's Least Circular Substrings
Input:
w[0..n-1] a word of length n
Output:
Index k such that w[k..n-1].w[0..k-1] ≤ w[i..n-1].w[0..i-1] for all 0 ≤ i ≤ n-1


T
r
y

i
t


w

f[0]←nil
k←0
for j←1 to 2n-1 do
i←f[j-k-1]
while w[j mod n] ≠ w[(k+i+1) mod n] and i ≠ nil do
if w[j mod n] < w[(k+i+1) mod n] then
k←j-i-1
i←f[i]
if w[j mod n] ≠ w[(k+i+1) mod n] and i = nil then
if w[j mod n] < w[(k+i+1) mod n] then
k←j
f[j-k]←nil
else
f[j-k]←i+1
return k
Reference
K. S. Booth
Lexicographically least circular substrings
Information Processing Letters, Volume 10, Issues 4-5, 5 July 1980, Pages 240-242

Valid XHTML 1.0 Strict CSS Valide !