『算法-ACM 竞赛』最小表示法

应用场景

一个首位相连的字符串，我们要寻找一个位置，从这个位置向后形成一个新字符串，我们需要使这个字符串字典序最小。

算法解释

我们这里要 i = 0,j = 1,k = 0,表示从 i 开始 k 长度和从 j 开始 k 长度的字符串相同（i，j 表示当前判断的位置）

当我们 str[i] == str[j]时，根据上面 k 的定义，我们的需要进行 k+1 操作

当 str[i] > str[j]时，我们发现 i 位置比 j 位置上字典序要大，那么不能使用 i 作为开头了，我们要将 i 向后移动，移动多少呢？有因为 i 开头和 j 开头的有 k 个相同的字符，那么就执行
i = i + k +1

相反 str[i] < str[j]时，执行：j = j + k +1

最终 i 和 j 中较小的值就是我们最终开始的位置

相反如果是最大表示法的话，我们就要求解字典序最大的字符串，那么我们只需要在执行第二或第三个操作时选择较大的那个位置较好了

实现

int n = strlen(s + 1);
for (int i = 1; i <= n; i++) s[n+i] = s[i];
int i = 1, j = 2, k;
while (i <= n && j <= n) {
	for (k = 0; k < n && s[i+k] == s[j+k]; k++);
	if (k == n) break; // s likes "aaaaa"
	if (s[i+k] > s[j+k]) {
		i = i + k + 1;
		if (i == j) i++;
	} else {
		j = j + k + 1;
		if (i == j) j++;
	}
}
ans = min(i, j);