最小表示法

似乎比较简单的算法。

1. 定义

一般是对于字符串而定义的。

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

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

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

暴力是 $O(n^2)$，我们可以通过该算法得到 $O(n)$ 的时间复杂度。

2. 思想

首先，这个相当于是一个环。

考虑破环为链，复制一倍接在后面，那么 $1\sim n$ 开始的长度为 $n$ 的字符串就是我们要找的。

我们最开始定义两个指针（差不多是双指针算法）：$i=1,j=2$。

直接暴力比较 $i$ 和 $j$ 开头的字符串的大小。

假设最后遇到了 $s_{i+k}>s_{j+k}$，那么以 $i$ 开头的一定不是最小表示法。

同时，我们可以发现，$[i+1,i+k]$ 任意开头的，仍然不是最小表示法。

明显的，我们找到 $[j+1,j+k]$，可以发现，对应的 $i$ 开头的，一定比对应的 $j$ 开头的更大。

这时，我们可以直接将 $i$ 跳到 $i+k+1$。

可以发现，时间复杂度和 $i,j$ 移动的长度是同级的，而显然，$i,j$ 的移动都是 $O(n)$ 的，所以时间复杂度为 $O(n)$。

但是，我们可能会遇到几个问题：

一直到 $k=n$ 的时候，都没有遇到 $s_{i+k}\not=s_{j+k}$：说明我们已经找到了更小的循环节，也就是已经遍历完了（后面都一样了）
$i\leftarrow i+k+1$ 后，$i=j$：$i\leftarrow i+1$，使两串错开。

就结束了。似乎也没有什么例题：

int main()
{
	for (int i = 1; i <= n; ++ i) str[i + n] = str[i];
	int i = 2, j = 1, k;
	while (i <= n && j <= n)
	{
		k = 0;
		while (k < n && str[i + k] == str[j + k]) k ++;
		if (k == n) break;
		if (str[i + k] < str[j + k]) j += k + 1;
		else i += k + 1;
		if (i == j) i ++;
	}
	int ans = min(i, j);
	for (k = ans; k <= ans + n - 1; ++ k) cout << str[k] << ' ';
	return 0;
}