也许令人惊讶的是，使用快速傅立叶变换（FFT）可以仅 在O（| A | nlog n）时间内
解决这个确切的问题，其中n是较大序列的长度，L并且|A|是字母的大小。

这是唐纳德·本森（Donald Benson）免费提供的一份PDF文件，描述了其工作原理：

• 用于生物序列分析的傅里叶方法（Donald Benson，《 核酸研究》 1990年第18卷，第3001-3006页）

总结： 转换每个串S和L为几个 指示器矢量 （每个字符之一，在DNA的情况下SO
4），然后进行卷积对应矢量，以确定每个可能的对准匹配计数。诀窍在于，通常可以使用O（n
^
2）时间的“时间”域中的卷积，而仅需O（n）时间加上转换所需的时间即可在“频率”域中使用乘法来实现域之间并再次返回。使用FFT，每次转换仅花费O（nlog
n）时间，因此总的时间复杂度为O（| A | nlog n）。为了达到最高速度，使用了 有限域 FFT，仅需整数运算即可。

注意： 对于任意算法S，L此算法显然比直接O（mn）算法具有巨大的性能优势，|S|并且|L|变得很大，但是OTOH
S通常短于log|L|（例如，当查询具有较小序列的大DB时），那么显然这种方法没有提供加速。

2009年7月21日更新 ：更新以提及时间复杂度还线性地取决于字母的大小，因为字母中的每个字符都必须使用一对单独的指示符向量。