Please Visit: http://ift.tt/1ajReyV
Lexicographically Minimal String Rotation | Algorithms NotesGiven 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
http://ift.tt/1jNsieqhttp://ift.tt/1yo5K6N
Lexicographically Minimal String Rotation | Algorithms Notes
from Public RSS-Feed of Jeffery yuan. Created with the PIXELMECHANICS 'GPlusRSS-Webtool' at http://gplusrss.com http://ift.tt/1jNskmA
via
LifeLong Community
