题目描述
给你一个字符串 s
,找出它的所有子串并按字典序排列,返回排在最后的那个子串。
样例
输入:"abab"
输出:"bab"
解释:
我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。
按字典序排在最后的子串是 "bab"。
输入:"leetcode"
输出:"tcode"
提示
1 <= s.length <= 10^5
s
仅含有小写英文字符。
算法
(字符串哈希,二分) $O(n \log n)$
- 所有的后缀子串,且以最大字母开头的字符串为备选串。
- 我们在这些备选串中找字典序最大的那一个,两个字符串的比较可以采用字符串哈希 + 二分的算法。
- 首先将字符串按照前缀哈希的方式进行哈希,即可以快速获取区间
[i, j]
的哈希值。这里采用了质数累乘和无符号整数自动溢出的做法(并不能保证不冲突,但冲突概率极低)。 - 比较两个字符串时,我们通过二分的方式,找到第一个不相同的位置,然后进行比较,并返回比较结果。
时间复杂度
- 构造哈希数组的时间复杂度为 $O(n)$,枚举二分的时间复杂度为 $O(n \log n)$,故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要额外空间存储哈希值,故空间复杂度为 $O(n)$。
C++ 代码
class Solution {
public:
string lastSubstring(string s) {
int n = s.size();
vector<unsigned> enc(n + 1, 0), power(n + 1);
power[0] = 1;
for (int i = 1; i <= n; i++) {
enc[i] = enc[i - 1] * 131 + s[i - 1] - 'a' + 1;
power[i] = power[i - 1] * 131;
}
auto cmp = [&](int x, int y) {
int len = min(n - x + 1, n - y + 1);
int l = 1, r = len;
while (l < r) {
int mid = (l + r) >> 1;
int hash_x = enc[x + mid - 1] - enc[x - 1] * power[mid];
int hash_y = enc[y + mid - 1] - enc[y - 1] * power[mid];
if (hash_x == hash_y)
l = mid + 1;
else
r = mid;
}
if (s[x + l - 2] != s[y + l - 2])
return s[x + l - 2] > s[y + l - 2];
return x < y;
};
char max_c = 'a';
for (int i = 0; i < n; i++)
max_c = max(max_c, s[i]);
int ans = 1;
for (int i = 2; i <= n; i++)
if (s[i - 1] == max_c && cmp(i, ans))
ans = i;
return s.substr(ans - 1, n - ans + 1);
}
};
居然可以用字符串哈希达到$log(N)$的比较算法,学到了。