Lexicographically minimal string rotation: Difference between revisions

Revision as of 07:32, 21 August 2020

Revision as of 15:03, 25 July 2022

Line 38:

<syntaxhighlight lang="python">

def least_rotation(S: str) -> int:

n = len(S)

"""Booth's algorithm."""

f = [-1] * len(S)2 * # Failure functionn)

S += S # Concatenate string to it self to avoid modular arithmetic

sjk = S[j]0

f = [-1] * len(S) # Failure function

for j in range(1, len(S)2 * n):

k = 0 # Least rotation of string found so far

for j in range(1, len(S)):

sj = S[j]

i = f[j - k - 1]

while i != -1 and sjS[j % n] != S[(k + i + 1) % n]:

if sjS[j % n] < S[(k + i + 1) % n]:

k = j - i - 1

i = f[i]

if sji !== -1 and S[kj +% i + 1n]: # if sj != S[(k + i + 1],) then% i == -1n]:

if sjS[j % n] < S[(k]: + #i k+i+ 1) =% kn]:

k = j

f[j - k] = -1