简单的缓和一下

最小表示法

定义

给定一个字符串 $S$ ，通过将 $S$ 循环移动可以得到至多 $n$ 个不同的串，其中 $n = |S|$ ，例如： $S = bcacd$ ，它循环移动一位可以得到 $S’ = cacdb$ （即把最后第一位放到最后）

对于得到的所有不同的字符串，字典序最小的串就叫原串的最小表示法，在上面的例子中， $S$ 的最小表示法为 $acdbc$

求法

最小表示法的求法比较简单，把字符串复制一倍接在原串后面（破环成链），然后用一个双指针 $i, j$ 指向两个不同串的开头，初始时 $i = 1, j = 2$ （假设字符串从1开始）

然后暴力找到一个最小的非负整数 $k$ 满足 $S_{i + k} \ne S_{j + k}$ ：

1. 若 $S_{i + k} < S_{j + k}$ ，则说明 $j \sim j + k$ 之间的所有位置开头的字符串都不是最小表示，因为它们都可以找到 $i \sim i + k$ 之间对应的开头的字符串，两个字符串到 $j + k$ （ $i + k$ ）前都相同，而 $S_{i + k} < S_{j + k}$ ，故直接令 $j = j + k + 1$
2. 若 $S_{i + k} > S_{j + k}$ ，同理令 $i = i + k + 1$

有几个特判：

1. $i = j$ 时，让 $i = i + 1$ （加 $j$ 也行）
2. $k > n$ 时，说明两个开头的串一样，画图不难发现此时 $i \sim j$ 一定时一个循环节，而 $i \sim j$ 我们一定遍历过，所以直接结束

完成后 $\min(i, j)$ 即为最小表示法的开头

时间复杂度为 $O(n)$

代码

int get_min(char *s) //求串s的最小表示,完成后答案存在s[k...k + len - 1]中
{
	int len = strlen(s + 1);
	for (int i = 1; i <= len; ++i)
		s[len + i] = s[i];
	int i = 1, j = 2, k;
	while (i <= len && j <= len)
	{
		k = 0;
		while (k <= len && s[i + k] == s[j + k])
			++k;
		if (k > len)
			break;
		if (s[i + k] > s[j + k])
			i += k + 1;
		else
			j += k + 1;
		if (i == j)
			++j;
	}
	k = min(i, j);
	s[k + len] = 0; //加上结束符
	return k;
}
//主函数中：
scanf("%s", a + 1);
int x = get_min(a);