找到到任何子串的最小汉明距离的最快方法？

给定一个长字符串L和一个较短的字符串S（约束条件是L.length 必须 >=S.length)，我想找到之间的最小汉明距离S和任意子串L长度等于S。长度。让我们为此调用该函数minHamming()。例如，

minHamming(ABCDEFGHIJ, CDEFGG) == 1.

minHamming(ABCDEFGHIJ, BCDGHI) == 3.

以显而易见的方式做到这一点（枚举 L 的每个子串）需要 O(S。长度 *L.长度）时间。有什么聪明的方法可以在亚线性时间内做到这一点吗？我搜索同样的L与几个不同的S字符串，因此需要进行一些复杂的预处理L一次是可以接受的。

编辑：修改后的 Boyer-Moore 将是一个好主意，除了我的字母表只有 4 个字母（DNA）。

也许令人惊讶的是，这个问题确实可以解决只需 O(|A|nlog n) 时间使用快速傅立叶变换 (FFT)，其中 n 是较大序列的长度L and |A|是字母表的大小。

以下是 Donald Benson 撰写的一篇论文的免费 PDF 文件，描述了它的工作原理：

• 用于生物序列分析的傅里叶方法（唐纳德·本森，核酸研究1990年卷。 18，第 3001-3006 页）

Summary:转换每个字符串S and L分成几个指示向量（每个字符一个，因此在 DNA 的情况下为 4），然后convolve相应的向量来确定每个可能的比对的匹配计数。诀窍在于，“时间”域中的卷积通常需要 O(n^2) 时间，可以使用“频率”域中的乘法来实现，这仅需要 O(n) 时间，加上转换所需的时间域之间并再次返回。使用 FFT，每次转换只需 O(nlog n) 时间，因此总体时间复杂度为 O(|A|nlog n)。为了获得最大速度，有限域使用 FFT，只需要整数运算。

Note:对于任意S and L与简单的 O(mn) 算法相比，该算法显然具有巨大的性能优势：|S| and |L|变大，但是 OTOH 如果S通常短于log|L|（例如，当使用小序列查询大数据库时），显然这种方法没有提供加速。

更新 21/7/2009：更新指出时间复杂度还线性取决于字母表的大小，因为字母表中的每个字符必须使用一对单独的指示向量。