信息竞赛进阶指南--最小表示法

应用场景

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

算法解释

我们这里要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);