FFT也能用于一些特殊的字符串匹配与最小化问题。
Prob 1 : 给出模式串A与文本串B，两个串中只有26个大写字母与通配符‘?‘（即可以任意匹配一个字符），求A在B中的匹配数。要求以FFT为例给出上限为O(nlogn)的算法。
Prob 2 : 给出模式串A与文本串B，字符集很小，求A在B中的匹配数，允许有k个字符不同。要求以FFT为例给出上限为O（nlogn*|S|）的算法。
Prob 3 : 给出数列a和b，长度均为n，a可以顺时针转动但不能翻转，最小化sigma(ai*bi)。
（未填完）
原文：https://www.cnblogs.com/GreenDuck/p/10585871.html