LeetCode·1163.按字典序排在最后的子串·最小表示法

链接：https://leetcode.cn/problems/last-substring-in-lexicographical-order/solution/by-xun-ge-v-xab4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

 

示例

 

思路

解题思路
最小表示法
关于最小表示法详细介绍可看链接 最小表示法详解

1. i = 0,j = 1,k = 0,表示从i开始k长度和从j开始k长度的字符串相同（i，j表示当前判断的位置）
2. 当str[i] == str[j]时，根据上面k的定义，需要进行k+1操作
3. 当str[i] > str[j]时，i位置比j位置上字典序要大，那么不能使用j作为开头了，我们要将j向后移动，移动多少呢？因为i开头和j开头的有k个相同的字符，那么就执行 j = j + k +1
4. 相反str[i] < str[j]时，执行：i = i + k +1
5. 若滑动后i == j，因为两个指针指向的内容都一样，则随意选一个加一以保证比较的两个字符串不同，并且重新开始，清空相同长度 k = 0

暴力求解

暴力枚举字符串每一个元素，判断元素大小

• 当元素大于最大元素时，保存下标，并且设置为最大元素
• 当元素等于最大元素时，判断之后字符字典序大小，保存字典序大的下标
• 当元素小于最大元素时，不处理

这里有个小技巧，当每次都判断之后字符字典序大小时，很显然会超时，但是限制一下每次判断之后字符的长度就不会了，限制长度这里设为20

代码

最小表示法

char * lastSubstring(char * s){
    int n = strlen(s);

    //最小表示法
    int k = 0, i = 0, j = 1;
    while (k < n && i+k < n && j+k < n) {
        if (s[i + k] == s[j + k]) {
            k++;
        } else {
            if(s[i + k] >= s[j + k])
            {
                j = j + k + 1;
            }else
            {
                i = i + k + 1;
            }
            if (i == j) i++;
                k = 0;
        }
    }
    i = fmin(i, j);

    return s+i;
}


作者：xun-ge-v
链接：https://leetcode.cn/problems/last-substring-in-lexicographical-order/solution/by-xun-ge-v-xab4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

暴力求解

char * lastSubstring(char * s){
    int len = strlen(s);
    int des = 0;
    char maxCh = s[0];
    for (int i = 1; i < len; i++) {//枚举每一个元素
        if (s[i] > maxCh) {//保存最大值
            maxCh = s[i];
            des = i;
        } else if (s[i] == maxCh) {//当元素等于最大元素时，判断之后字符字典序大小，保存字典序大的下标
           des = (strncmp(s+des, s+i, 20) >= 0) ? des : i;
        }
    }

    return s+des;
}


作者：xun-ge-v
链接：https://leetcode.cn/problems/last-substring-in-lexicographical-order/solution/by-xun-ge-v-xab4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。