找到任何子串的最小汉明距离的最快方法？
问题内容：
给定一个长字符串L和一个短字符串S（约束是L.length必须> =
S.length），我想找到与长度等于.length的S任何子字符串之间的最小汉明距离。让我们为此调用函数。例如，L``S``minHamming()
minHamming(ABCDEFGHIJ, CDEFGG) == 1。
minHamming(ABCDEFGHIJ, BCDGHI) == 3。
这样做很明显（枚举L的每个子串）需要O（S.length * L.length）时间。在亚线性时间内，有什么聪明的方法可以做到这一点吗？我L用几个不同的S字符串搜索相同的内容，因此L一次进行一些复杂的预处理是可以接受的。
编辑：修改过的Boyer-Moore是一个好主意，除了我的字母只有4个字母（DNA）。
问题答案：
也许令人惊讶的是，使用快速傅立叶变换（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日更新 ：更新以提及时间复杂度还线性地取决于字母的大小，因为字母中的每个字符都必须使用一对单独的指示符向量。
