LeetCode每日一题（2023/4/24）

1163. 按字典序排在最后的子串

给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

 

示例 1：

输入：s = "abab"
输出："bab"
解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。
示例 2：

输入：s = "leetcode"
输出："tcode"
 

提示：

1 <= s.length <= 4 * 10^5
s 仅含有小写英文字符。

解答：二分

class Solution {
    int P = 131;
    long[] p;
    long[] h;
    String s;
    int n;

    public long get(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
    //二分判断a和b的字典排序
    public boolean cmp(int a, int b) {
        int l = 0;
        int r = n - b + 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (get(a, a + mid - 1) == get(b, b + mid - 1)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        if (l == n - b + 1) {
            return false;
        }
        return s.charAt(a + l - 1) < s.charAt(b + l - 1);
    }

    public String lastSubstring(String s) {
        this.s = s;
        this.n = s.length();
        p = new long[n + 1];
        h = new long[n + 1];
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] * P;
            h[i] = h[i - 1] * P + (s.charAt(i - 1) - 'a');
        }
        int res = 1;
        for (int i = 2; i <= n; i++) {
            if (cmp(res, i)) {
                res = i;
            }
        }
        return s.substring(res - 1);
    }
}