最小最大表示法超详细讲解

前言

最小/最大表示法是用来找出字符串的最小/最大字典序的循环同构串的方法，其求解算法可以达到O(N)，过程很像KMP算法的next数组推导过程，都是在暴力解法的基础上省去了冗余操作。

循环同构串

学习最小/最大表示法，先要了解循环同构串的概念。

给定长度为n字符串S，将其当作环形字符串，则给定i（0 <= i <= n- 1），s[ i ] , s[(i + 1) % n] … s[(i + n - 1) % n]所构成的新字符串就是S的一个循环同构串。
设S= “bcad”，其循环同构串有"bcad"、“cadb” 、“adbc” 、“dbca”,
当i = 2时，得到字典序最小的循环同构串是“adbc"。
最小/最大表示法就是找出字符串S的循环同构串中字典序最小/最大的那一个。

最小表示法

对于循环串(或环)，我们可以选择直接将其倍增一次，但是倍增的空间其实可以通过下标取模来优化掉。

(倍增后)s[i + k] = (倍增前)s[(i + k) % n]

暴力解法

暴力解法流程：

• 两个指针i，j分别代表两个循环同构串的起始位置
• 当i串的字典序大于j串，i = max(i + 1, j + 1)
• j串字典序小于i串j = max(i + 1, j + 1)
• 当i == j时，j++
• 最终取二者中小的那个就是答案

代码如下：

    //string s;
    int i = 0, j = 1, k, n = s.size();
    while (i < n && j < n)
    {
        for (k = 0; k < n && s[(i + k) % n] == s[(j + k) % n]; k++)
            ;
        if (s[(i + k) % n] > s[(j + k) % n])
            i = max(i + 1, j + 1);
        else
            j = max(i + 1, j + 1);
        if (i == j)
            j++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

要进行n - 1次比较，时间复杂度为O(N^2)

暴力解法的可优化之处

还是类比KMP算法，我们KMP算法就是对略去了暴力字符串匹配中的冗余操作而达到了O(M + N)的时间复杂度，那么我们的暴力寻找最小循环同构串的过程有没有冗余之处呢？

我们发现每次j都是从j的下一个位置重新进行匹配，有没有一种可能我们之前匹配过的字符可以跳过或者说跳过部分呢？

我们以S = "acacaba"为例

上图情况中按照暴力解法，i应该跳转到j + 1，也就是c的位置，跳转后的字典序显然仍小于j串，于是还要继续跳转到a的位置，我们发现此时i跳到了第一次比较失败的下一个位置

我们不禁想当比较失败时，指针是否可以直接跳转到比较失败的下一个位置呢？

我们假设i < j，此时i串字典序小于j串，在i + k 和 j + k的地方匹配失败

那么在i和j之间的部分，j能达到j的位置说明i和j之间的部分字典序显然大于i串，所以不必跳转到此区间

而 j 到i+k之间的部分，我们发现j 到 i + k是i串和j串的最长公共前缀，如果有字符小于s[ i ]，那么由于前缀的对应关系我们最终会得到s[ i ] < s[ i ]的结论，显然不对，所以我们的优化策略就是i直接跳转到i + k + 1的位置

优化后，每次扫描k个长度，相应的i和j会往后移动k，i，j合计一共最多往后移动2n的长度，所以时间复杂度是O(n)

最小表示法的代码实现

算法流程：

1. 初始化指针i=0，j=1，匹配长度k=0;
2. 比较s[(i+ k)%n]和s[(j+k)%n]是否相等,
3. (1)s[(i+ k)%n]==s[(j+k)%n]，则k++;
4. (2)s[(i+ k)%n] > s[(j+k)%n]，则i=i+k+1;
5. (3)s[(i+ k)%n] < s[(j+k)%n]，则j=j+k+1;
6. 若跳转后两个指针相同，则j++，以确保比较的两个字符串不同;
7. 重复上述过程，直到比较结束;
8. 答案为min(i, j)。

    int i = 0, j = 1, k, n = s.size();
    while (i < n && j < n)
    {
        for (k = 0; k < n && s[(i + k) % n] == s[(j + k) % n]; k++)
            ;
        if (s[(i + k) % n] > s[(j + k) % n])
            i = i + k + 1;
        else
            j = j + k + 1;
        if (i == j)
            i++;
    }
    i = min(i, j);
1
2
3
4
5
6
7
8
9
10
11
12
13

最大表示法

最大表示法和最小表示法的原理一样，只要修改代码中的条件即可

代码如下

    int i = 0, j = 1, k, n = s.size();
    while (i < n && j < n)
    {
        for (k = 0; k < n && s[(i + k) % n] == s[(j + k) % n]; k++)
            ;
        if (s[(i + k) % n] < s[(j + k) % n])
            i = i + k + 1;
        else
            j = j + k + 1;
        if (i == j)
            i++;
    }
    i = min(i, j);
1
2
3
4
5
6
7
8
9
10
11
12
13