先考虑如何数一个串中小于 $s$ 的子串个数，你试图扫描线，不妨让一个子串被数到当且仅当经过第一个不同的位置（或者末尾），也就说明你只需要关心 $l$ 是后面还有多少个，以及已经填过的前缀中与 $s$ 某个前缀相等的最长后缀长度，是否 $s$ 已经出现和当前已经确定的小于 $s$ 的子串个数。我们调整下可以证明若存在 $t$ 则最短的 $\lvert t\rvert$ 不超过 $2k$（考虑称满足 $\forall j\leq i,\, t[j,i]\geq s$ 的 $i$ 为关键点，则一定有任意包含关键点的区间不造成贡献，而且 $s$ 的一次出现一定满足除去最后一位均为非关键点，因此极小的方案不能有相邻两个关键点，开头也不能是关键点，而至多 $k$ 个非关键点，因此得证），所以状态数是 $\mathcal{O}(nk^2)$ 的，而且转移只用枚举填 $0$ 还是 $1$，转移边数与点数同阶。

也就是说如果你只是要检验是否存在长度为 $l$ 的串的话你可以做到 $\mathcal{O}(lk^2)$，而且你发现只在意是否有解所以可以变成 $\mathcal{O}(\frac{lk^2}{w})$，构造方案只需要记录下来所有递推结果然后倒着找方案即可，而且你还知道如果有解就存在 $l\leq 2k$。

那你就可以发现转置一下，变成从起点 $(0,?,1,k)$ 走到 $(l,0,0,0)$，直接 bitset 优化维护可达性即可。