建出 AC 自动机，直接消元可以在 $O((nm)^3)$ 的时间里求出从每个点开始走到终止状态的期望时间。注意到点 $u$ 列出的方程只会涉及到 $u$ 在 Trie 上的孩子和一些深度不超过 $u$ 的点。如果 $u$ 只有一个孩子，则可以把这个孩子用其他的点表示出。因此把根和有兄弟的点作为关键点，则每个点都能用一些关键点表示出，而变量数减少到了 $O(n)$。总复杂度 $O(n^2mk+n^3+|R|)$。