Lexical minimal string rotation

a.cpp

std::string minimum_representation(std::string S)
{
	int i = 0, j = 1, n = S.size();
	S += S;
	while (j < n)
	{
		int k = 0;
		while (j+k < 2*n && S[i+k] == S[j+k]) ++k;
		if (j+k == 2*n)
			break;
		else if (S[i+k] > S[j+k])
			i = std::max(i+k+1, j), j = i+1;
		else
			j += k+1;
	}
	return std::string(S, i, n);
}

设 S = ss，两个指针 i，j。 如果从 a 开始的字典序小于从 b 开始的字典序，则称 a 优于 b。

循环不变式 [0,i),(i,j) 均不是最优解。

初始化 令 i = 0，j = 1。

保持 如果 S[i:END] == S[j:END]，说明 [i,j) 是一个循环节。由周期性可知，i 是一个最优解。 否则，令 k 为满足 S[i+k] != S[j+k] 的最小自然数。

• S[i+k] > S[j+k]
  • i,i+1,…,i+k 均不是最优解，它们分别劣于 j,j+1,…,j+k。 再结合循环不变式，可知 [0,j),[0,i+k] 中均不是最优解。 令 i’ = max(j,i+k+1)，j’ = i’+1。
• S[i+k] < S[j+k]
  • j,j+1,…,j+k 均不是最优解。 令 j’ = j+k+1。

终止 如果曾经有 S[i:] == S[j:]，由上知 i 是一个最优解。 否则，j >= |s| 时终止，i 也是最优解。

Credit: https://chrt.github.io/2017/07/06/min-repr/