最小表示法

[Ir1d]

https://oi-wiki.org/string/minimal-string/

[partychicken]

自己占楼

[Lagos-Ren]

资瓷

[GreyTigerOIer]

最小表示法其实可以用后缀数组做的，复杂度也可以到O(n)

[develop-er-OI-ACM]

@MrFoodinChina
最小表示法其实可以用后缀数组做的，复杂度也可以到O(n)
后缀数组的时间复杂度是O(nlogn)

[scp020]

错误的，sa可以做到O(n)

[hfhongzy]

@develop-er-OI-ACM

@MrFoodinChina
最小表示法其实可以用后缀数组做的，复杂度也可以到O(n)
后缀数组的时间复杂度是O(nlogn)

使用SA-IS做到O(n)

[develop-er-OI-ACM]

@hfhongzy 谢谢，涨姿势了。

[rsx-sbaby]

博主你好，问一下，为什么答案是（i,j)的较小值，i不行吗

[GreyTigerOIer]

@rsx-sbaby
博主你好，问一下，为什么答案是（i,j)的较小值，i不行吗

因为你是随机选一个跳啊，有可能你跳了之后$i>j$了就会出问题

[GreyTigerOIer]

@develop-er-OI-ACM

@MrFoodinChina
最小表示法其实可以用后缀数组做的，复杂度也可以到$O(n)$
后缀数组的时间复杂度是$O(nlogn)$

后缀数组有$O(n)$做法的

[jerryqiang]

不不不，想了下，还是需要求min(i, j)

Java代码如下所示：

public static int[] getMin(int[] arr) {
    int i = 0;
    int j = 1;
    int k = 0;
    int n = arr.length;
    while (i < n && j < n && k < n) {
        if (arr[(i + k) % n] < arr[(j + k) % n]) {
            j = j + k + 1;
            k = 0;
        } else if (arr[(i + k) % n] > arr[(j + k) % n]) {
            i = i + k + 1;
            k = 0;
        } else {
            k++;
        }
        if (i == j) {
            j++;
        }
    }
    i = Math.min(i, j);
    int[] res = new int[arr.length];
    for(k = 0; k < arr.length; k++) {
        res[k] = arr[(i + k) % n];
    }
    return res;
}

[thahao]

最后return 的不应该是 sec[i]<sec[j]?i:j 吗

[jerryqiang]

最后return 的不应该是 sec[i]<sec[j]?i:j 吗

假设arr.length为n
i或者j可能到达边界n，arr[i]或者arr[j]索引取值会报越界错误，
例如[5, 4, 3, 2, 1]求最小表示法
因此直接返回起始索引小的序号即可，索引小的表示也越小

[PJSSABER]

跳的时候可以一直保证 i < j来跳嘛？ 先让 i = j; j++

[imarkzzz]

始终保证 i < j 的写法

def get_min(s):
    n = len(s)
    i, j = 0, 1
    while j < n:
        k = 0
        while k < n and s[(i + k) % n] == s[(j + k) % n]:
            k += 1
        if s[(i + k) % n] > s[(j + k) % n]:
            i, j = j, max(j + 1, i + k + 1)
        else:
            j = j + k + 1
    return s[i:] + s[:i]

[imarkzzz]

证明过程参考leetcode.1163. 按字典序排在最后的子串