-
Notifications
You must be signed in to change notification settings - Fork 1.8k
/
Rotation.java
94 lines (87 loc) · 3.48 KB
/
Rotation.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package com.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 <[email protected]>
* @author Justin Wetherell <[email protected]>
*/
public class Rotation {
private static char charAt(String text, int pos) {
pos = pos % text.length();
return text.charAt(pos);
}
private static int compare(char a, char b, boolean greater) {
if (a == b)
return 0;
return (a < b) ^ greater ? -1 : 1;
}
private static String bestRotation(String text, boolean greatest) {
if (text.length() < 2)
return text;
final int n = text.length() * 2;
int k = 0;
int i = 0, j = 1;
while (i + k < n && j + k < n) {
final char a = charAt(text, i+k);
final char b = charAt(text, j+k);
final int comp = compare(a, b, greatest);
if (comp == 0) {
k++;
} else if (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;
}
}
final int pos = i < j ? i : j;
return text.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
*/
public static String getLexicographicallyMinimalRotation(String text) {
return bestRotation(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
*/
public static String getLexicographicallyMaximalRotation(String text) {
return bestRotation(text, true);
}
}