最小表示法模板

我们定义循环是指不断将第一个字符放到最后。

显然，经过循环之后，一共会产生 $n$ 个字符串（ $n$ 为字符串长度）。

其中最小的就是最小表示法。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int n, s[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &s[i]);
    for (int i = 1; i <= n; i++)
        s[i + n] = s[i];
    int t = -1;
    for (int i = 2, j = 1; i <= n && j <= n; )
    {
        int k = 0;
        while (k < n && s[i + k] == s[j + k]) k++;
        if (k == n) { t = min(i, j); break; }
        (s[i + k] < s[j + k] ? j : i) += k + 1;
        if (i == j) ++i;
    }
    for (int i = t; i <= t + n - 1; i++)
        printf("%d ", s[i]);
    return 0;
}