显然我们确定最终答案和 $A$ 的匹配后，$\tt ?$ 直接换成匹配字符、匹配空串的 $\tt *$ 直接删掉后，仍然满足要求，且长度不会变长。

因此答案形如 $({\tt *})s_1{\tt *}s_2{\tt *}\cdots{\tt *}s_k({\tt *})$，如果开头和结尾都有 *，那么判断匹配只需要每次当前位置之后选择出现最早的 $s_i$。开头和结尾没有 ${\tt *}$ 需要稍微特判。

设 $dp(i,j)$ 为使得 $A,B$ 当前分别匹配到 $i,j$ 的最小模式串长度（假设结尾有 $\tt *$）。首先可以直接转移到 $(i+1,j)$，也就是 $A_i$ 匹配上一个 $\tt *$。否则要添加一个新的串，我们枚举 $k$，添加串 $A[i,k)$，那么需要找到 $B$ 中 $j$ 之后下一个出现位置，转移到 $(k,r)$。如果不存在下一个出现位置，就可以直接作为答案。注意要特判开头和结尾没有 $\tt *$ 的情况，对应要求出现位置必须是前缀或后缀。

预处理 $A$ 和 $B$ 每个后缀的 LCP 之后，倒序枚举 $j$，可以 $O(1)$ 转移，时间复杂度 $O(|A|^2|B|)$。