特殊性质 A

暴力枚举所有长度 $\le 15$ 的串即可。

特殊性质 B

对于全 $0$ 串，只有长度比其短的全 $0$ 串才会在字典序上比其小。因此可以将答案串 $T$ 拆成若干个连续的全 $0$ 段，便可统计 $T$ 中有多少个子串的字典序严格小于 $S$。

反向构造求解时，只需借助背包 DP 即可完成转移，从而通过特殊性质 B。

特殊性质 C 与特殊性质 D

该特殊性质与正解逻辑同源，主要区别在于这两个特殊性质的状态转移相对直观，而正解需要借助 KMP 自动机。以下直接阐述正解。

完整解法

对于一个串 $T$，定义 $B(T) = \max \{j \vert S[1,j]=T[|T|-j+1,|T|]\}$，即 $T$ 的后缀与 $S$ 的前缀能够匹配的最大长度，等效于 $T$ 在针对 $S$ 构建的 KMP 自动机上的匹配状态；定义 $A(T)=\{x \vert T[x,|T|] < S \land x<|T|-B(T)+1\}$，表示已经不参与匹配，且已确定以其为起点的子串字典序必然小于 $S$ 的左端点集合。同时记录 $C(T)$ 为当前 $T$ 中字典序小于 $S$ 的子串数量。

实际上，只需记录状态 $(|A|,B,C)$ 就能在不断向 $T$ 末尾添加字符的情况下转移至新状态 $(|A'|,B',C')$。因此，问题转化为求出状态图上 $(0,0,0)\to (0,0,k)$ 的最短路径。

为辅助转移，需预处理三维数组 $r_{i,j,c}$ 表示：有多少个 $k$ 满足 $S[k,i]$ 拼接上字符 $c$ 后字典序严格小于原 $S$。该预处理的时间复杂度为 $O(|S|^2)$。

状态转移规则如下（以下直接用 $A$ 指代 $|A|$）：

• 若当前状态为 $(A,B,C)$，且即将追加字符 $c \in \{0, 1\}$。
• 令 $B'$ 为状态 $B$ 在 KMP 自动机上接受字符 $c$ 的出边所指向的新状态。
• 那么 $A'=A+r_{B,B-B'+1,c}$，$C'=C+A'+r_{B,B+1,c}$。
• 得到的新状态即为 $(A',B',C')$。

值得注意的是，由于题目限制 $T$ 必须包含 $S$ 作为子串，因此还需在状态中加入一维布尔变量，用于记录路径中是否曾经到达过 $B=|S|$ 的状态。

据此建图并求解最短路即可。由于边权均为 $1$，直接在状态图上 BFS 即可得出答案。

算法复杂度分析如下（设 $n = |S|$）：

• 状态 $B$ 的范围是 $O(n)$，状态 $C$ 的范围是 $O(k)$。
• 分析维度 $A$：当某位置 $j$ 在时刻 $t$ 被纳入集合 $A$ 时，其已经对 $C$ 产生了 $t-j$ 的必然贡献。这意味着，集合 $A$ 中的所有元素给 $C$ 带来的累计贡献下界为 $\sum_{i=0}^{|A|-1} i = O(|A|^2)$。
• 由此可推导出，状态 $A$ 的规模受到 $A=O(\sqrt{C})=O(\sqrt{k})$ 的限制。
• 综上，状态总数被界定在 $O(nk \sqrt{k})$ 级别。

因此总的时间与空间复杂度均为 $O(n^2+nk \sqrt{k})$。