最小表示法-526互联

存在 $i$ ，使得 $S[i,n]+S[1,i-1] =T$ 我们称为循环同构。

若 $S$ 的字典序最小的表示 $T$ 则称为最小表示法。

暴力求法：我们已经知道 $S$ 和 $T$ 为循环同构，我们钦定 $i,j$ 表示两种不同的开始方法，枚举步数 $k$ ，如果存在 $S_{(i+k)\mod n} = S_{(j+k)\mod n}$，$k$ 增加，否则比较字典序, 字典序大的那一个开头增加，最后取 $\min$ 即可。

int k = 0, i = 0, j = 1;
while (k < n && i < n && j < n) {
  if (sec[(i + k) % n] == sec[(j + k) % n]) {
    ++k;
  } else {
    if (sec[(i + k) % n] > sec[(j + k) % n])
      ++i;
    else
      ++j;
    k = 0;
    if (i == j) i++;
  }
}
i = min(i, j);

可能会被卡，并不推荐使用，最劣为 $O(n^2)$。

优化：很明显，存在 $S[i,(i+k)\mod n -1] = S[j,(j+k) \mod n-1]$ 。所以，字典序大的一方从起点到这里均不可能为最大答案，因为之后不管怎么样，到这个位置一定会有更优的最小表示（$j$ 已经帮你试过了，如果你再和 $j$ 相等，没有意义）。比如 $S_{(i+k) \mod n } \gt S_{(j+k) \mod n} $ ，$S[i,(i+k)\mod n]$ 的均不可能是最小表示。复杂度 $O(n)$ 。

int k = 0, i = 0, j = 1;
while (k < n && i < n && j < n) {
  if (sec[(i + k) % n] == sec[(j + k) % n]) {
    k++;
  } else {
    sec[(i + k) % n] > sec[(j + k) % n] ? i = i + k + 1 : j = j + k + 1;
    if (i == j) i++;
    k = 0;
  }
}
i = min(i, j);