Problem：A21317

令模式串为 $S$，文本串为 $T$，通配符数量为 $k$。

你谷题解区都是 $O(nk(|S|+|T|))$ 的，看看能不能去掉一些东西。

首先把最左边的 * 左边和最右边的 * 右边的字符都给匹配了，变成 *...* 的样子。

我们按 * 分段，依次匹配，显然越早匹配越优。

现在就转化成了如何匹配带 ? 的字符串。

如果你直接将 ? 当万能的一起跑 KMP，就会出问题。比如说 hack：

*bab?bab*
1
babbabbbaba

你会发现前 $4$ 个是没问题的，但是匹配到 $T_5$ 的时候，需要跳 next，但是此时 $S$ 的 ba 和 $T$ 的 bb 匹配了！

现在如果要判断是否失配，需要将所有原先匹配 ? 的位置全都判一遍，复杂度又带上 $k$。

那咋办，只能考虑复杂度带 $k$ 的了。

然后我们发现好像可以把 ? 也划分了，然后给每一段匹配。

所以考虑对这个跑一个 ACAM，加上偏移看第一个可以匹配到底的是哪个位置。

然后我们惊喜地发现，这个可以 bitset。

然后就可以 $O(|S||\Sigma|+n(|S|+|T|)+\frac{nk|T|}{w})$，去掉 $64$ 也是去，嗯。字符集算常数，嗯。

代码，会写的，吧。