If the strings represent potentially isomorphic structures such as graphs, normalizing in this way allows for simple equality checking.
Of interest is that removing all lines of code which modify the value of k results in the original Knuth-Morris-Pratt preprocessing function, as k (representing the rotation) will remain zero.
comparisons in the worst case, and requires auxiliary memory of length n to hold the failure function table.
The first phase is a quick sieve which rules out indices that are obviously not starting locations for the lexicographically minimal rotation.
The second phase then finds the lexicographically minimal rotation start index from the indices which remain.
Duval (1983)[4] proposed an efficient algorithm involving the factorization of the string into its component Lyndon words, which runs in linear time with a constant memory requirement.
Shiloach (1979)[5] proposed an algorithm to efficiently compare two circular strings for equality without a normalization requirement.
An additional application which arises from the algorithm is the fast generation of certain chemical structures without repetitions.