菜王的 blog

记号

设 $s[l, r]$ 为字符串 $s$ 从第 $l$ 位到第 $r$ 位构成的字串。

有一个长度为 $n$ 的字符串 $s$，如果我们不断把它开头的字符移到结尾，可以得到 $n$ 个字符串，这些字符串是循环同构的，其中字典序最小的就是 $s$ 的最小表示。

我们可以把 $s$ 复制一份接在后面，将新字符串记作 $ss$。

显然，查询时，可以直接查询 $ss[i, i + n - 1]$ 来得到第 $i$ 个循环同构串。

如何求出 $s$ 的最小表示呢？

我们可以暴力比较 $s$ 的所有循环同构串，时间复杂度为 $O(n^2)$。

我们可以维护两个变量 $i$，$j$，分别代表 $ss[i, i + n - 1]$ 和 $ss[j, j + n - 1]$。$i$，$j$ 分别初始为 $1$，$2$。

比较可以直接使用一个变量 $k$，按位比较 $ss[i + k - 1]$ 与 $ss[j + k - 1]$ 的值。

这个做法明显有优化的空间，怎么优化呢？

我们先看一个例子。

有一个字符串 $s$ 为 abcabb，$ss$ 则为 abcabbabcabb。

现在 $i = 4$，$j = 1$，$k = 3$。

我们发现 $ss[6] < ss[3]$。

通过这一位的大小，我们可以得出很多的信息：

$ss[6] < ss[3]$，不仅意味着 $ss[4, 9] < ss[1, 6]$，还意味着 $ss[5, 10] < ss[2, 7]$，$ss[6, 11] < ss[3, 8]$。

综上所述，当 $ss[i] < ss[j]$ 时，因为 $ss[i, i + k - 2] = ss[j, j + k - 2]$ 且 $ss[i + k - 1] < ss[j + k - 1]$，所以对于 $l \in [j, j + k - 1]$， $ss[l, l + n - 1] > ss[i, i + n - 1]$。

于是，发现差异时，可以直接将那个对应字符较大的变量后移 $k$ 位。

由于 $i$ 和 $j$ 都只会右移，且都最多只会右移 $n$ 次，时间复杂度为 $O(n)$。

代码

模板题代码：

#include <cstdio>
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)

int n, a[600001], ans;
int main(){
	scanf("%d", &n);
	for (int i = 1;i <= n;i ++) scanf("%d", &a[i]), a[i + n] = a[i]; // 复制一份接在后面
	int i = 1, j = 2;
	for (;i <= n && j <= n;){
		int k = 0;
		for (;a[i + k] == a[j + k];) k ++; // 匹配
		if (a[j + k] < a[i + k]){
			int t = j;
			j = max(j + 1, i + k + 1); // 右移（这里取 max 是为了防止前移）
			i = t;
		}
		else j = j + k + 1;
		// 注意，这里保证了 j 始终 > i
	}
	for (int _ = i;_ < i + n;_ ++) printf("%d ", a[_]); // 输出
}