我正在研究一个脚本，该脚本能够对字符串中的某个模式进行近似匹配，仅报告这些模式（它们可能重叠）启动的位置。
到目前为止，我已经获得了一个脚本，该脚本能够报告完全匹配的位置，但是对于近似的位置却没有成功：
import re
stn = 'KLHLHLHKPLHLHLPHHKLHKLPKPH'
pat = 'KLH'
matches = re.finditer(r'(?=(%s))' % re.escape(pat), stn)
finalmatch= [m.start() for m in matches]
pos = ' '.join(str(v) for v in finalmatch)
print pos
在这种情况下的结果是：
0 17
但是如果脚本报告也近似匹配怎么办？即，如果最大允许错误（公差或阈值）为1（在查询模式的任何位置），如何报告HLH，PLH，KLP，KPH的初始位置？
我已经尝试过包括Levenshtein或SequenceMatcher之类的距离度量，但是没有成功。
在此先感谢您的帮助。
最佳答案
基本方法：
将stn个连续块的n个字符分组，其中n是len(ptn)
计算每个块和ptn之间有多少个相同的字符
开始了解其中有多少个字符与len(ptn)不同
例如：
stn = 'KLHLHLHKPLHLHLPHHKLHKLPKPH'
pat = 'KLH'
n_combos = zip(*[stn[n:] for n in range(len(pat))])
m_counts = (sum(1 for i, j in zip(el, pat) if i == j) for el in n_combos)
indices = [idx for idx, val in enumerate(m_counts) if val >= len(pat) - 1]
# [0, 2, 4, 8, 10, 17, 20, 23]