Lexicographically Minimal String Rotation | Algorithms Notes

http://geeksquiz.com/lexicographically-minimum-string-rotation/
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

def LCS(S):
    S += S      # Concatenate string to it self to avoid modular arithmetic
    f = [-1]*len(S)     # Failure function
    k = 0       # Least rotation of string found so far
    for j in range(1, len(S)):
        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

https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation
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.

https://github.com/LukasFolwarczny/insalg/blob/master/code/string-minlexrot.cpp
int step(int i, char c) {
if (St(k+i+1) == c) {
return i+1;
}
if  (i >= 0) {
if (c < St(k+i+1)) //
k = j-i-1; //
return step(F[i], c);
}
if (c < St(k+i+1)) k = j; //
return -1;

}

// Returns the number of positions to left shift to get the
// lexicographically minimal rotation.
int minlexrot(char S[]) {
N = strlen(S);
_S = S;
F = (int*)malloc(N*sizeof(int));
F[0] = -1;
k = 0;
for (j = 1; j < 2*N; j++) {
if (j - k >= N) return k;
F[j-k] = step(F[j-k-1], St(j));
}
free(F);
}
http://geeksquiz.com/lexicographically-minimum-string-rotation/
O(n2Logn):
1) Concatenate ‘str’ with itself and store in a temporary string say ‘concat’.
2) Create an array of strings to store all rotations of ‘str’. Let the array be ‘arr’.
3) Find all rotations of ‘str’ by taking substrings of ‘concat’ at index 0, 1, 2..n-1. Store these rotations in arr[]
4) Sort arr[] and return arr[0].

string minLexRotation(string str)

{

    // Find length of given string

    int n = str.length();

 

    // Create an array of strings to store all rotations

    string arr[n];

 

    // Create a concatenation of string with itself

    string concat = str + str;

 

    // One by one store all rotations of str in array.

    // A rotation is obtained by getting a substring of concat

    for (int i = 0; i < n; i++)

        arr[i] = concat.substr(i, n);

 

    // Sort all rotations

    sort(arr, arr+n);

 

    // Return the first rotation from the sorted array

    return arr[0];

}

Read full article from Lexicographically Minimal String Rotation | Algorithms Notes