给定一个长字符串L和一个较短的字符串S(约束条件是L.length必须>= S .length)，我想找到 S 和长度等于 S 的 L 的任何子字符串之间的最小汉明距离。长度。让我们调用此 minHamming() 的函数。例如，
minHamming(ABCDEFGHIJ, CDEFGG) == 1。
minHamming(ABCDEFGHIJ, BCDGHI) == 3。
以显而易见的方式(枚举 L 的每个子串)需要 O(S.length * L.length) 时间。有什么聪明的方法可以在次线性时间内做到这一点吗？我用几个不同的 S 字符串搜索相同的 L，所以对 L 进行一些复杂的预处理是可以接受的。
编辑:修改后的 Boyer-Moore 是个好主意，除了我的字母表只有 4 个字母 (DNA)。
最佳答案
也许令人惊讶的是，使用快速傅里叶变换 (FFT)，这个确切的问题可以在 O(|A|nlog n) 时间内解决，其中 n 是较大序列的长度 L 和 |A| 是字母表的大小。
这是唐纳德·本森 (Donald Benson) 描述其工作原理的一篇论文的免费 PDF 文件:
- Fourier methods for biosequence analysis (唐纳德·本森，核酸研究 1990 年第 18 卷，第 3001-3006 页)
总结:将每个字符串 S 和 L 转换为多个指示器向量(每个字符一个，所以 4 在 DNA 的情况下)，然后是 convolve相应的向量以确定每个可能对齐的匹配计数。诀窍在于，通常需要 O(n^2) 时间的“时间”域中的卷积可以使用“频率”域中的乘法来实现，这只需要 O(n) 时间，加上转换所需的时间域之间并再次返回。使用 FFT 每次转换仅需 O(nlog n) 时间，因此整体时间复杂度为 O(|A|nlog n)。为了获得最快的速度，使用了有限域 FFT，它只需要整数运算。
注意:对于任意S 和L，此算法显然比直接的 O(mn) 算法具有巨大的性能优势，因为 |S| 和 |L| 变大了，但是 OTOH 如果 S 通常比 log|L| 短(例如当查询具有小序列的大型数据库时)，那么显然这种方法没有提供加速。
2009 年 7 月 21 日更新:更新后提到时间复杂度也线性取决于字母表的大小，因为必须为字母表中的每个字符使用一对单独的指示向量.
关于performance - 找到到任何子串的最小汉明距离的最快方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33557060/