考虑在 $C$ 当中 $A$ 和 $B$ 的位置关系，讨论每种情况，取其中字典序最小的即可：

• $A$ 完全被 $B$ 包含：可以用 KMP 判断。然后相当于把 $B$ 和剩下的字符排列使得字典序最小，也就是考虑 $B$ 的开头字符 $x$ 和第一个不等于 $x$ 的字符 $y$，如果 $y>x$，则所有小于等于 $x$ 的字符都应该排在 $B$ 之前；如果 $y< x$，则所有小于 $x$ 的字符都应该排在 $B$ 之前。

• $A$ 和 $B$ 不相交：也是把一些串排列使得字典序最小，一定是 $AB\le BA$ 时 $A$ 排在 $B$ 之前，剩下的字符和第一种情况类似。

• $A$ 和 $B$ 相交：不妨设 $A$ 的后缀和 $B$ 的前缀相交。满足条件的前后缀可以对 $BA$ 做 KMP 求出。首先需要满足 $C$ 当中有足够的字符，也就是这个 border 的长度必须大于某个值。接下来考虑如何比较两个 border 做为相交部分的字典序大小关系：

  • 根据之前的分析，一定存在某个 $x$ 使得小于等于 $x$ 的字符会排在 $A$ 之前（注意这里事实上有 $A$ 所有字符相同的情况，这时候只需要看 $B$ 中第一个不等于 $A_1$ 的字符），所以如果两个 border 相差的部分中有小于等于 $x$ 的字符，则较长的 border 一定更优。

  • 设两个 border 分别为 $S$ 和 $ST$，$B=STX$，如果 $T$ 当中没有小于等于 $x$ 的字符，则只需要比较 $TX$ 和 $X$ 的字典序大小（$X$ 可能是 $TX$ 的前缀，这时还需要往后比较，但这时多出来的字符一定可以拼出来等于 $TX$，所以选择 $X$ 不会更劣）。考虑 border 形成了 $O(\log |B|)$ 个等差数列，每一段当中要比较的串都形如 $T^kX$，字典序的最小值一定是在 $k$ 取最小或最大时取到。

    上述分析结合起来，可以得到统一的结论：当 border 长度满足字符数量的限制时，答案一定是在等差数列的端点处取到。

时间复杂度 $O((X+Y+Z)\log Y)$。还可以用 Z 函数实现 $O(1)$ 比较两个 border 的优劣（因为是 border，上面的 $S$ 一定是 $ST$ 的后缀，因此我们只需要比较 $STX=B$ 和 $SX$，其中 $SX$ 是 $B$ 的后缀，用 Z 函数即可 $O(1)$ 比较），做到线性复杂度。