若后缀 [i..|t|) 的字典序不比 s 小：\
若 s 为后缀 [i..|t|) 的前缀，则该后缀长度小于 |s| 的前缀字典序都比 s 小。\
否则可以找到最小的 p 满足 s_{p}<t_{i+p}，则该后缀长度小于 p 的前缀字典序都比 s 小。
不难得出：对于已有的 t，当我们尝试在结尾添加字符进行转移时，后缀 [i..|t|) 的贡献形式未确定当且仅当该后缀为 s 的前缀。因为若不为前缀，当该后缀的字典序比 s 小时，每往 s 加入一个字符，该后缀就会贡献一个字典序比 s 小的子串；当该后缀的字典序不比 s 小时，无论怎么往 s 里加入字符，该后缀都不会贡献字典序比 s 小的子串。
可以据此写出状态定义：f(i,j,k,0/1) 表示当前 t 最长的为 s 前缀的后缀长度为 i，目前已经确定 t 有 j 个子串字典序比 s 小，每添加一个字符会使 j 增加 k，s 尚未/已经作为 t 子串出现过的最短 t 长度。
对于转移，考虑在 t 结尾添加一个字符 0/1，对 i,j,k 的影响可以在建 KMP 自动机的同时计算。具体地，i 在 KMP 自动机跳转时可能变小为 p，这时长度在 [p+1,i] 中的后缀的贡献形式由未知变为已知，由于 n 很小，i 变化对 j 和 k 的贡献可以暴力计算，我写的是 O(n^3) 处理这部分贡献。
因为转移只会使 dp 值增加 1，因此可以按照状态的 bfs 序转移。
统计答案时要注意，t 长度 \le i 的后缀，它贡献的 字典序比 s 小的子串数 是没有被加到 j 中的，最后统计答案时要把这部分加上。
这个有效状态数我算不来😂，但根据实践大概是 O(nm\sqrt m) 的，我个人认为这是因为 j 的增长会随 k 的增长越来越快导致的，希望有大佬能给出证明思路或 hack 思路。