-
Notifications
You must be signed in to change notification settings - Fork 46
Expand file tree
/
Copy pathLastSubstringInLexicographicalOrder.java
More file actions
131 lines (111 loc) · 4.15 KB
/
Copy pathLastSubstringInLexicographicalOrder.java
File metadata and controls
131 lines (111 loc) · 4.15 KB
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/**
* Last Substring in Lexicographical Order
*
* Suffix Array
*/
import java.util.Arrays;
public class LastSubstringInLexicographicalOrder {
static class SuffixArray {
private char str[];
private int MAX_LOG = 30;
private int n, nr0[], nr1[], rank[][], index[], step, cnt;
private int M;
private int minusOneHead;
private int minusOneTail;
private int bucketHead[];
private int bucketTail[];
private int pointTo[];
private int next[];
private int globalPtr;
public SuffixArray(String s) {
str = s.toCharArray();
n = str.length;
nr0 = new int[n];
nr1 = new int[n];
index = new int[n];
rank = new int[MAX_LOG][n];
M = Math.max(128, n);
bucketHead = new int[M];
bucketTail = new int[M];
pointTo = new int[M];
next = new int[M];
for (int i = 0; i < n; i++)
rank[0][i] = str[i];
boolean needSort = true;
for (step = cnt = 1; (cnt >> 1) < n; step++, cnt <<= 1) {
if (!needSort) {
for (int i = 0; i < n; i++)
rank[step][i] = rank[step - 1][i];
continue;
}
for (int i = 0; i < n; i++) {
nr0[i] = rank[step - 1][i];
nr1[i] = i + cnt < n ? rank[step - 1][i + cnt] : -1;
index[i] = i;
}
radixSort1();
radixSort0();
needSort = false;
for (int i = 0; i < n; i++) {
if (i > 0 && nr0[index[i]] == nr0[index[i - 1]] && nr1[index[i]] == nr1[index[i - 1]]) {
rank[step][index[i]] = rank[step][index[i - 1]];
needSort = true;
} else rank[step][index[i]] = i;
}
}
}
private void radixSort0() {
globalPtr = 0;
Arrays.fill(bucketHead, -1);
Arrays.fill(next, -1);
for (int i = 0; i < n; i++) {
int value = nr0[index[i]];
if (bucketHead[value] == -1) bucketHead[value] = bucketTail[value] = globalPtr;
else bucketTail[value] = next[bucketTail[value]] = globalPtr;
pointTo[globalPtr++] = index[i];
}
int ptr = 0;
for (int i = 0; i < M; i++)
for (int j = bucketHead[i]; j != -1; j = next[j])
index[ptr++] = pointTo[j];
}
private void radixSort1() {
globalPtr = 0;
Arrays.fill(bucketHead, -1);
Arrays.fill(next, -1);
minusOneHead = minusOneTail = -1;
for (int i = 0; i < n; i++) {
int value = nr1[index[i]];
if (value == -1) {
if (minusOneHead == -1) minusOneHead = minusOneTail = globalPtr;
else minusOneTail = next[minusOneTail] = globalPtr;
} else {
if (bucketHead[value] == -1) bucketHead[value] = bucketTail[value] = globalPtr;
else bucketTail[value] = next[bucketTail[value]] = globalPtr;
}
pointTo[globalPtr++] = index[i];
}
int ptr = 0;
for (int j = minusOneHead; j != -1; j = next[j])
index[ptr++] = pointTo[j];
for (int i = 0; i < M; i++)
for (int j = bucketHead[i]; j != -1; j = next[j])
index[ptr++] = pointTo[j];
}
public int lcp(int x, int y) {
int k, ret = 0;
if (x == y) return n - x;
for (k = step - 1; k >= 0 && x < n && y < n; k--)
if (rank[k][x] == rank[k][y]) {
x += 1 << k;
y += 1 << k;
ret += 1 << k;
}
return ret;
}
}
public String lastSubstring(String s) {
SuffixArray sa = new SuffixArray(s);
return s.substring(sa.index[s.length() - 1]);
}
}