Given a string S with length n, design a linear time algorithm to find the lexicographically minimal string among all rotation of S.
Solution:
The idea is to find the minimal string rotation in S[1..j] in increasing order of j. Let k be the starting position of the minimal string rotation in S[1..j]. Let i be the length of the longest suffix of S[1..j] satisfies S[k..k+i-1] = S[j-i+1..j]. If S[j+1] < S[k+i], then it means S[j-i+1..j+1] is smaller than S[k..k+i] and hence j-i+1 is the starting position of the minimal string rotation in S[1..j+1]. Since the length of the longest suffix equals the prefix of S[k..k+n] can be computed in a way similar KMP in linear time, the total complexity is linear.
This problem can be solved in linear time with O(1) space
Read full article from Lexicographically Minimal String Rotation | Algorithms Notes
No comments:
Post a Comment