Rotation.java

packagecom.jwetherell.algorithms.strings;

/**
 * Rotation of the string is some cyclic transformation of that string.
 * More formally a string s = uv is said to be a rotation of t if t = vu.
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/String_(computer_science)#Rotations">String Rotation (Wikipedia)</a>
 * <br>
 * @Author Szymon Stankiewicz <mail@stankiewicz.me>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
publicclassRotation {

privatestaticcharcharAt(Stringtext, intpos) {
pos = pos % text.length();
returntext.charAt(pos);
 }

privatestaticintcompare(chara, charb, booleangreater) {
if (a == b) 
return0;
return (a < b) ^ greater ? -1 : 1;
 }

privatestaticStringbestRotation(Stringtext, booleangreatest) {
if (text.length() < 2)
returntext;

finalintn = text.length() * 2;
intk = 0;
inti = 0, j = 1;
while (i + k < n && j + k < n) {
finalchara = charAt(text, i+k);
finalcharb = charAt(text, j+k);
finalintcomp = compare(a, b, greatest);
if (comp == 0) {
k++;
 } elseif (comp > 0) {
i += k+1;
if (i <= j )
i = j + 1;
k = 0;
 } else {
j += k+1;
if (j <= i)
j = i + 1;
k = 0;
 }
 }
finalintpos = i < j ? i : j;
returntext.substring(pos) + text.substring(0, pos);
 }

/**
 * Finds lexicographically minimal string rotation.
 * Lexicographically minimal string rotation is a rotation of a string possessing the
 * lowest lexicographical order of all such rotations.
 * Finding the lexicographically minimal rotation is useful as a way of normalizing strings.
 * <p>
 * @see <a href="https://https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation">Lexicographically Minimal String Rotation (Wikipedia)</a>
 * <p>
 * This function implements Duval's algorithm.
 * <p>
 * @see <a href="https://https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation#Duval.27s_Lyndon_Factorization_Algorithm">Duval's Algorithm (Wikipedia)</a>
 * <p>
 * Complexity: O(n)
 * <br>
 * @param text
 * @return lexicographicall minimal rotation of text
 */
publicstaticStringgetLexicographicallyMinimalRotation(Stringtext) {
returnbestRotation(text, false);
 }

/**
 * Finds lexicographically maximal string rotation.
 * Lexicographically maximal string rotation is a rotation of a string possessing the
 * highest lexicographical order of all such rotations.
 * Finding the lexicographically maximal rotation is useful as a way of normalizing strings.
 * <p>
 * @see <a href="https://https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation">Lexicographically Minimal String Rotation (Wikipedia)</a>
 * <p>
 * This function implements Duval's algorithm.
 * @see <a href="https://https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation#Duval.27s_Lyndon_Factorization_Algorithm">Duval's Algorithm (Wikipedia)</a>
 * <p>
 * Complexity: O(n)
 * <br>
 * @param text
 * @return lexicographicall minimal rotation of text
 */
publicstaticStringgetLexicographicallyMaximalRotation(Stringtext) {
returnbestRotation(text, true);
 }
}