最小表示法

最小表示法

字符串 \(S\) 的最小表示为与 \(S\) 循环同构的所有字符串中字典序最小的字符串。

一般用于判断两个字符串是否循环同构。只需要都用最小表示，然后判断即可。

考虑如何构造。这里oiwiki解释的很清楚。就不做过多解释了。复杂度\(O(n)\)

int i = 1, j = 2, k;
while (i <= n && j <= n) {
    for (k = 0; k < n && a[i + k] == a[j + k]; ++k);
    if (k == n)break;
    if (a[i + k] > a[j + k]) {
        i = i + k + 1;
        if (i == j)i++;
    } else {
        j = j + k + 1;
        if (i == j)j++;
    }
}

例题：
luogu: P1368 【模板】最小表示法

这题有很多方法可以解决，比如SA，SAM，Lyndon 分解。之后会提到，值得注意的是，最小表示不一定是Lyndon 分解后的最后一个串，但是洛谷数据并没有卡掉这种写法