Lexicographically minimal string rotation: Difference between revisions

Revision as of 18:25, 17 April 2012

Revision as of 03:26, 19 April 2012

Line 39:

def LCS(S):

n = len(S)

fS += [-1S for c in S] # Concatenate string #to self to Failureavoid functionmodular tablearithmetic

kf = n [-1 for c in S] # Initial rotationFailure indexfunction

while (k-1) != 0 and S[k-1] == S[0]: # #Least rotation of string found Errorso correctionfar

k -= 1

k %= n

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

i = f[j-k-1]

ifwhile j-ki >!= n:-1 and S[j] != # Least circular shift foundS[k+i+1]:

if S[j%ni] <= S[(k+i+1)%n] and i != -1: # Error correction

k = j-i-1

return k

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

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

k = j-i-1

i = f[i]

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

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

k = j

f[j-k] = -1

else:

f[j-k] = i+1

return k

</source>

Of interest is that removing all lines of code which modify the value of '''''k''''' results in the original Knuth-Morris-Pratt preprocessing function, as '''''k''''' (representing the rotation) will remain zero. The algorithm presented in the original paper contained several critical bugs; the lines in the above implementation commented "Error correction" fix them. Booth's algorithm runs in '''''O(n)''''' time, where '''''n''''' is the length of the string. The algorithm performs at most '''''3n''''' comparisons in the worst case, and requires auxiliary memory of length '''''n''''' to hold the failure function table.

===Shiloach's Fast Canonization Algorithm===