题目描述

给你两个带通配符的串 $A,B$。问 $B$ 中可以匹配多少个 $A$,并输出匹配的开头位置。

思路

我们在两个长度相同的字符串 $A, B$ 上定义 $f(A, B)=\sum_{i=0}^{n-1}(A_i – B_i)^2A_iB_i$。令通配符 * 为 0,当 $f(A,B)=0$ 时,$A = B$。

将 $f$ 展开得 $\sum_{i=0}^{n-1} \left( {A_i}^3B_i – 2 {A_i}^2{B_i}^2 + A_i{B_i}^3 \right)$。

我们将 $A$ 翻转得到 $A’$,那么上式等于 $\sum_{i=0}^{n-1} ( {A’_{n-i-1}}^3B_i – 2 {A’_{n-i-1}}^2{B_i}^2 + A’_{n-i-1}{B_i}^3)$,就将这个式子变换成为了卷积的形式。

做七遍 FFT ,输出所有答案为 $0$ 的下标即可。

代码