长度为n的循环字符串中找字典序最小的长度为n的子串

考虑对于一对字符串 $A,B$, 它们在原字符串 $S$ 中的起始位置分别为 $i,j$, 且它们的前 $k$ 个字符均相同，即$S[i \cdots i+k-1]=S[j \cdots j+k-1]$

不妨先考虑 $S[i+k]>S[j+k]$ 的情况，我们发现起始位置下标 $l$ 满足 $i\le l\le i+k$ 的字符串均不能成为答案。因为对于任意一个字符串 $S_{i+p}$（表示以 $i+p$ 为起始位置的字符串，$p \in [0, k]$）一定存在字符串 $S_{j+p}$ 比它更优。

所以我们比较时可以跳过下标 $l\in [i,i+k]$, 直接比较 $S_{i+k+1}$

string fun(string s) {   
    int a=0, b=1, c=0, n=s.size();
    while (a<n && b<n && c<n) {
        if (s[(a+c)%n] == s[(b+c)%n]) {
            c++;
        } else {
            if (s[(a+c)%n] > s[(b+c)%n]) a += c+1;
            else b += c+1;
            if (a == b) a++;
            c=0;
        }
    }
    a = min(a, b);
    return s.substr(a)+s.substr(0, a);
}

寻找字符串中字典序最大的子串

最大子串必定是原串的后缀

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

class Solution {
public:
    string lastSubstring(string s) {
        int a=0, b=1, c=0, n=s.size();
        while (a+c<n && b+c<n) {
            if (s[a+c] == s[b+c]) {
                c++;
            } else {
                if (s[(a+c)%n] < s[(b+c)%n]) a += c+1;
                else b += c+1;
                if (a == b) a++;
                c=0;
            }
        }
        a = min(a, b);
        return s.substr(a);
    }
};