给定字符串 s, 求它的所有循环移位中, 字典序最小者. 下标从 0 开始.
设 S = ss, 两个指针 i, j. 如果从 a 开始的字典序小于从 b 开始的字典序, 则称 a 优于 b.
循环不变式 [0,i),(i,j) 均不是最优解.
初始化 令 i = 0, j = 1.
保持 如果 S[i:] == S[j:], 说明 [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 也是最优解.
会不会出现 i >= |s| 的情况呢? 不会, 因为我们一直保持着循环不变式, 而 i 和 i mod |s| 是等同的.
算法的时间复杂度是 O(n). 内部 while 循环执行 k 次, 之后 i 或 j 增加至少 k+1. 由此看出, 内部的 while 循环执行总次数不超过 3n.
int minimum_representation(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 = max(i+k+1, j), j = i+1;
else
j += k+1;
}
return i;
}