注意到在最终的 $X$ 中，每个 $S_i$ 的贡献是一个子串，且除了第一个贡献非空的串以外都是前缀；如果第一个贡献非空的串是 $S_1$，则必须是后缀，否则可以是任意子串。

考虑 $f(i,j)$ 表示使用串 $S_i,\ldots,S_n$ 的各一个前缀按顺序拼接的长度为 $j$ 的字典序最小的串。可以发现 $f(i,j)$ 一定是某个串 $T_i$ 的前缀。这是因为，首先 $f(i,j)$ 单调递增，因为我们一定能去掉一个更长的串的后缀，得到一个更短的串；且更短的串不可能在某个位置严格小于更长的串，否则一定可以在其后添加一些字符得到更长的串。注意这个结论只有在前缀的情况下才满足，因为如果能选择任意子串，开头位置可能太靠后，导致无法添加足够的字符。

因此我们 DP 过程中只需要保存 $T_i$，转移时只需要计算 $S_i$ 的一个前缀和 $T_{i+1}$ 的一个前缀拼接起来的最小长度为 $M$ 的串，也就是让这个前缀和 $T_{i+1}$ 直接拼接起来字典序最小。更新答案也是类似的，假设第一个有贡献的串是 $S_i$，则选择的子串的起始位置一定是 $S_i+\infty$ 的字典序最小的后缀，其中 $\infty$ 是一个比其余字符都大的字符；如果是 $S_1$，只需要计算 $S_1+T_{2}$ 字典序最小的长度为 $M$ 的子串，可以用类似最小表示法的方式解决，或者直接 $O(M^2)$ 暴力。

如何计算 $S$ 的一个前缀拼上 $T$ 之后字典序最小的串？我们先找到答案第一个小于 $S$ 的位置，假设是 $S_i$，这就要求 $S[1:i-1]$ 的一个后缀要匹配上 $T$ 的一个前缀，且 $T$ 的下一个字符小于 $S_i$，这很容易用 KMP 判断。此时匹配的一定是 $T$ 的一个前缀的 border，我们要比较的是 $T$ 在去掉前缀的这段 border 之后的字典序。注意到因为是 border，设两个 border 分别是 $X,Y$（$|X|<|Y|$），则要比较的是 $T[|X|+1:]$ 和 $T[|Y|+1:]$ 的大小，而因为 border 的性质，$X$ 是 $Y$ 的后缀，所以也等价于比较 $T$ 和 $T[|Y|-|X|+1:]$ 的大小，这可以用 Z 函数在线性时间内完成。

综上所述，我们在 $O(NM)$ 的时间内解决了这个问题。