修改后的Boyer-Moore算法
我找到了一些旧的Python实现Boyer-Moore算法，并修改了匹配循环（在该循环中将文本与模式进行比较）。不是在两个字符串之间发现第一个不匹配就退出，而是简单地计算不匹配数量，但记住第一个不匹配：
current_dist = 0
while pattern_pos >= 0:
if pattern[pattern_pos] != text[text_pos]:
if first_mismatch == -1:
first_mismatch = pattern_pos
tp = text_pos
current_dist += 1
if current_dist == smallest_dist:
break
pattern_pos -= 1
text_pos -= 1
smallest_dist = min(current_dist, smallest_dist)
if current_dist == 0:
return 0
else:
pattern_pos = first_mismatch
text_pos = tp
...
如果此时字符串没有完全匹配，通过恢复值回到第一个不匹配的点。这可以确保找到最小距离。
整个实现相当长（~150 LOC），但我可以根据要求发布它。核心思想已经概述了，其他一切都是标准的Boyer-Moore算法。
在文本上进行预处理是另一种加速的方法，可以在字符位置上建立索引。您只想从至少发生两个字符串之间单个匹配的位置开始比较，否则Hamming距离就是|S|。
import sys
from collections import defaultdict
import bisect
def char_positions(t):
pos = defaultdict(list)
for idx, c in enumerate(t):
pos[c].append(idx)
return dict(pos)
该方法仅创建一个字典，将文本中的每个字符映射到其出现次数排序后的列表。
比较循环与朴素的 O(mn) 方法基本相同，除了我们不是每次将比较开始位置增加 1，而是根据字符位置进行增加。
def min_hamming(text, pattern):
best = len(pattern)
pos = char_positions(text)
i = find_next_pos(pattern, pos, 0)
while i < len(text) - len(pattern):
dist = 0
for c in range(len(pattern)):
if text[i+c] != pattern[c]:
dist += 1
if dist == best:
break
c += 1
else:
if dist == 0:
return 0
best = min(dist, best)
i = find_next_pos(pattern, pos, i + 1)
return best
实际的改进在于
find_next_pos函数：
def find_next_pos(pattern, pos, i):
smallest = sys.maxint
for idx, c in enumerate(pattern):
if c in pos:
x = bisect.bisect_left(pos[c], i + idx)
if x < len(pos[c]):
smallest = min(smallest, pos[c][x] - idx)
return smallest
对于每个新的位置，我们找到S中出现在L中的字符的最低索引。如果没有这样的索引了，算法将终止。
find_next_pos肯定很复杂，可以尝试通过仅使用模式S的前几个字符或使用集合来确保不会检查两次来改进它。
讨论
哪种方法更快主要取决于您的数据集。字母表越多样化，跳跃就越大。如果L非常长，则预处理的第二种方法可能更快。对于非常短的字符串（例如您的问题），朴素的方法肯定是最快的。
DNA
如果您的字母表非常小，可以尝试获取字符二元组（或更大）的字符位置，而不是单个字符。
