2020-03-13 13:48:05
问题描述：
给你一个字符串 s，找出它的所有子串并按字典序排列，返回排在最后的那个子串。
示例 1：
输入："abab"
输出："bab"
解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。
示例 2：
输入："leetcode"
输出："tcode"
提示：
1 <= s.length <= 4 * 10^5
s 仅含有小写英文字符。
问题求解：
首先看数据规模，暴力求解是肯定不行的。时间复杂度基本在O(n) / O(nlogn)级别可以通过。
本题有个点非常重要就是最大的子串一定是其后缀，试想如果最大的子串不是后缀，那么往后追加字符必然比它本身大，矛盾。
但是仅仅观察到这一步暴力求解依然只能作出O(n ^ 2)的解，如何更进一步呢？
想到后缀自然就想到后缀数组，如果使用倍增法，可以在O(nlogn)得到解，如果使用DC3/SA-IS可以在O(n)得到解，可行。
另外，本题还可以转化为字符串的最大表示，本质上是一样的。
简单的来说，字符串的最大表示和最小表示类似，就是遇到小的直接跳过即可，采用这种算法可以在O(n)的时间复杂度得到解。
方法一：字符串的最大表示
时间复杂度：O(n)
public String lastSubstring(String s) {
int n = s.length();
int i = 0;
int j = 1;
int k = 0;
while (i < n && j < n && k < n) {
int diff = s.charAt((i + k) % n) - s.charAt((j + k) % n);
if (diff == 0) k++;
else {
if (diff > 0) j = j + k + 1;
else i = i + k + 1;
k = 0;
if (i == j) j++;
}
}
return s.substring(Math.min(i, j), n);
}
方法二：后缀数组-倍增
时间复杂度：O(nlogn)
public String lastSubstring(String s) {
int n = s.length();
Integer[] sa = new Integer[n + 1];
int[] rank = new int[n + 1];
for (int i = 0; i <= n; i++) {
sa[i] = i;
rank[i] = i == n ? -1 : s.charAt(i);
}
for (int k = 1; k < n; k *= 2) {
int offset = k;
Arrays.sort(sa, new Comparator<Integer>(){
public int compare(Integer o1, Integer o2) {
if (rank[o1] != rank[o2]) return Integer.compare(rank[o1], rank[o2]);
else {
int r1 = o1 + offset <= n ? rank[o1 + offset] : -1;
int r2 = o2 + offset <= n ? rank[o2 + offset] : -1;
return Integer.compare(r1, r2);
}
}
});
int[] new_rank = new int[n + 1];
new_rank[sa[0]] = 0;
for (int i = 1; i <= n; i++) {
new_rank[sa[i]] = new_rank[sa[i - 1]];
if (!isEqual(rank, sa[i], sa[i - 1], k)) new_rank[sa[i]]++;
}
for (int i = 0; i <= n; i++) {
rank[i] = new_rank[i];
}
}
return s.substring(sa[n]);
}
boolean isEqual(int[] rank, int i, int j, int k) {
int n = rank.length;
if (rank[i] != rank[j]) return false;
int r1 = i + k <= n ? rank[i + k] : -1;
int r2 = j + k <= n ? rank[j + k] : -1;
return r1 == r2;
}