#0.0 前置知识

#0.1 循环同构

当字符串 \(S\) 中存在一个位置 \(i\) 使得

则称 \(S\) 与 \(T\) 循环同构。

#0.2 最小表示

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

#1.0 朴素算法

思想很简单，我们每次比较 \(i\) 和 \(j\) 开始的循环同构，把当前比较到的位置记作 \(k\)，每次遇到不一样的字符时便把大的跳过，最后剩下的就是最优解。

伪代码如下：

最后的 \(i\) 就是最小表示的起始位置。上面的做法在随机数据的情况下表现良好，但如同 \(aaaa\cdots ab\) 的数据便可以将上述代码的时间复杂度卡至 \(O(n^2).\)

#2.0 最小表示法

#2.1 算法流程

考虑对于两个字符串 \(A,B\)，如果他们在原字符串 \(S\) 中的起始位置分别为 \(i,j\)，且其前 \(k\) 位相等，即

那么假设 \(S[i+k]>S[j+k]\)，那么，不难发现，对于任意一个起始位置 \(l\) 满足 \(i\leq l\leq i+k\) 的字符串 \(A‘\)，一定存在一个对应的 \(B‘\) ，起始位置 \(r\) 满足 \(j\leq r\leq j+k\)，\(B‘\) 的字典序小于 \(A‘\) 的字典序。

所以，我们可以直接跳过 \([i+1,i+k]\) 这一段区间，直接从 \(i+k+1\) 开始新的比较。整个算法与上文朴素算法的唯一区别就在这里，是最关键的一点。

#2.2 代码实现

inline int solve() {
    int k = 0, i = 0, j = 1;
    while (k < n && i < n && j < n) {
        if (a[(i + k) % n] == a[(j + k) % n]) k ++;
        else {
            if (a[(i + k) % n] < a[(j + k) % n])
              j = j + k + 1;
            else i = i + k + 1;
            k = 0; if (i == j) i ++;
        }
    }
    return Min(i, j);
}

参考资料

[1] 最小表示法 - OI Wiki

[2] 最小表示法 详解+模板+例题 - Cervusky

[字符串入门]最小表示法

原文：https://www.cnblogs.com/Dfkuaid-210/p/14966975.html