An efficient algorithm was proposed by Booth (1980).[2] The algorithm uses a modified preprocessing function from the Knuth-Morris-Pratt string search algorithm. The failure function for the string is computed as normal, but the string is rotated during the computation so some indices must be computed more than once as they wrap around. Once all indices of the failure function have been successfully computed without the string rotating again, the minimal lexicographical rotation is known to be found and its starting index is returned. The correctness of the algorithm is somewhat difficult to understand, but it is easy to implement.
def LCS(S): n = len(S) S += S # Concatenate string to self to avoid modular arithmetic f = [-1 for c in S] # Failure function k = 0 # Least rotation of string found so far for j in range(1, 2*n): i = f[j-k-1] while i != -1 and S[j] != S[k+i+1]: if S[j] < S[k+i+1]: k = j-i-1 i = f[i] if i == -1 and S[j] != S[k+i+1]: if S[j] < S[k+i+1]: k = j f[j-k] = -1 else: f[j-k] = i+1 return k
Read full article from Lexicographically minimal string rotation - Wikipedia, the free encyclopedia
No comments:
Post a Comment