Lexicographically Minimal String Rotation | Algorithms Notes Given a string S with length n, design...

Please Visit: http://ift.tt/1ajReyV

Lexicographically Minimal String Rotation | Algorithms Notes



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

http://ift.tt/1jNsieq

http://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