最小表示法使用于解决字符串最小表示问题的方法。何为字符串的最小表示呢？

循环同构：当字符串 $S$ 中任意位置 $i$ 满足 $S[i\sim n]+S[1\sim i-1]=T$，称 $S$ 与 $T$ 循环同构。

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

求解算法

朴素算法

每次比较 $i$ 和 $j$ 开始的循环同构，把当前比较到的位置记作 $k$，每次遇到不同的字符时便把大的跳过，最后剩下的就是最优解。

实现：

int min_rep(string s) {
    int n = s.size(), i = 0, j = 1, k = 0;
    while (k < n && i < n && j < n) {
        if (s[(i + k) % n] == s[(j + k) % n]) k++;
        else {
            if (s[(i + k) % n] > s[(j + k) % n]) i++;
            else j++;

            k = 0;
            if (i == j) i++;
        }
    }

    return min(i, j);
}

优化算法

考虑一对字符串 $A,B$，它们在原字符串 $S$ 中的起始位置分别为 $i,j$，且它们前 $k$ 个字符均相同，即 $S[i\sim i+k-1]=S[j\sim j+k-1]$。

如果 $S[i+k]>S[j+k]$，则对于起始下标 $l$ 满足 $i\le l\le i+k$ 的循环同构串均不能成为答案，这是因为对于任意一个字符串 $S_{i+p}$ （表示以 $i+pp\in [0,k]$ 为起始位置的循环同构串），一定存在字符串 $S_{j+p}$ 比它更优。所以此时我们可以之间跳过下标 $l\in [i,i+k]$ 直接比较 $S_{i+k+1}$。反之同理。

int min_rep(string s) {
    int n = s.size(), i = 0, j = 1, k = 0;

    while (k < n && i < n && j < n) {
        if (s[(i + k) % n] == s[(j + k) % n]) k++;
        else {
            if (s[(i + k) % n] > s[(j + k) % n]) i = i + k + 1;
            else j = j + k + 1;

            k = 0;
            if (i == j) i++;
        }
    }

    return min(i, j);
}