3605. Minimum Rotations
Some explanation: all rotations of S are in the beginning of S' suffixes from positions between 0 and length(S) - 1. Suffix array keeps suffixes in lexicographical order, so you just need to pick the first one which begins from rotation of S.
Given string A, add the string to itself.
Compute the suffix array of only first half. (use the characters of second half also)
the smallest suffix gives the minimum lexicographic rotation of a string.
Also check
http://www.spoj.com/problems/MINMOVE/
http://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=756
Read full article from algorithm - Minimum Lexicographic Rotation Using Suffix Array - Stack Overflow
Given a string S[1..n] . A rotation on S is that we move the first character to the right-most of the string. More specific, after a rotation, S becomes T = S[2..n] + S[1].
For example: S = abcaa, then after a rotation we have S = bcaaa.
Find the minimum number of rotations to make S become the smallest lexicographical order string.
It seems that you should take first suffix in SA, which index is between 0 and length(S) - 1.Some explanation: all rotations of S are in the beginning of S' suffixes from positions between 0 and length(S) - 1. Suffix array keeps suffixes in lexicographical order, so you just need to pick the first one which begins from rotation of S.
Given string A, add the string to itself.
Compute the suffix array of only first half. (use the characters of second half also)
the smallest suffix gives the minimum lexicographic rotation of a string.
Also check
http://www.spoj.com/problems/MINMOVE/
http://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=756
Read full article from algorithm - Minimum Lexicographic Rotation Using Suffix Array - Stack Overflow
