FFT 解决字符串匹配问题 朴素的字符串匹配 设有两个字符串 $a,b$ 长度分别为 $n,m (n\geq m)$ ，询问字符串 $b$ 在 $a$ 中出现了几次。 这是一个最基础的字符串匹配问题，显然我们容易想到 $O (nm)$ 的暴力匹配方法，同时也可以使用 $KMP$ 算法在 $O (n+m)$ 的复杂度下解决该问题。实际上，我们还可以利用 $F…