作者：whisper

链接：http://proprogrammar.com:443/article/382

声明：请尊重原作者的劳动，如需转载请注明出处

    最小与最大只是判断条件不一样，其实质是一样的，以最小表示法为例。

    用途：

    给出一个字符串，求与它循环同构的串中字典序最小的串

    求一个字符串的最大（小）后缀子串

    下面给出最小表示法的java实现

int minRepresent(String s) {
    int i = 0, j = 1, k = 0, len = s.length();
    while (i < len && j < len && k < len) {
        int t = s.charAt((i+k) % len) - s.charAt((j+k) % len);
        if (t == 0) {
            k++;
        }else {
            if (t < 0){
                j = Math.max(j+k+1, i+1);
            }else{
                i = Math.max(i+k+1, j+1);
            }
            k = 0;
        }
    }
    return Math.min(i, j);
}

    算法解释

• 令i=0,j=1表示最小的字符串可能的位置；
•      找到一个k使得s[i+1]==s[j+1],s[i+2]==s[j+2] ,..., s[i+k-1]==s[j+k-1] ;
•      但是s[i+k]!=s[j+k];
•      如果此时s[i+k]<s[j+k]，对于j' = j + 1 到 j + k 的位置一定不是最优解，因为i+j'-j位置的串一定比j'位置的更优；且如果i+j'-j位置的串更优一定会被i选到。那么我们就可以 j=j+k+1
•     s[i+k]>s[j+k]就i=i+k+1,注意i==j时要再向后移动一位
•     事实上你可以理解成i和j是互相独立的只是其中的某一个为最小的串的待定值，另一个为用来比较的串；

     解释一下为什么i, j取值时会是Math.max()的形式，对i，j两个可能的最小子串位置，当出现t != 0的情况时，说明其中一处不满足最小子串的条件，不妨设i处不满足，此时可能的最小子串位置是j，所以另一个可能的最小子串位置一定在j的后面，j的前面可不可能呢，不可能，如果可能最小子串位置就不会是到j，而是在j前的那个位置了，能到j说明从i+1到j-1的位置都不是最小子串位置，此时i不满足条件，可能位置一定在j之后，又上面分析知i+1到i+k也不会是最小子串位置，所以最小子串位置是Math.max(i+k+1, j+1)，对j位置不满足最小子串时的分析也一样

    最后给出最大表示法的实现

int minRepresent(String s) {
    int i = 0, j = 1, k = 0, len = s.length();
    while (i < len && j < len && k < len) {
        int t = s.charAt((i+k) % len) - s.charAt((j+k) % len);
        if (t == 0) {
            k++;
        }else {
            // t与0的关系是最大表示法与最小表示法唯一的不同
            if (t > 0){
                j = Math.max(j+k+1, i+1);
            }else{
                i = Math.max(i+k+1, j+1);
            }
            k = 0;
        }
    }
    return Math.min(i, j);
}

亲爱的读者：有时间可以点赞评论一下