原文链接：http://ginstrom.com/scribbles/2007/12/01/fuzzy-substring-matching-with-levenshtein-distance-in-python/
编辑距离是模糊字符串匹配领域广为人知的一项技术。经过一些改动，编辑距离同样可以用于子串的模糊匹配。
例子：
子串：“abc”
匹配对象：“c abba c”
直观的看出“aba”能够匹配“abba”，以下是这些字符串之间的 编辑距离：
右下角的5就是两个字符串之间的编辑距离。这是从“aba”到“c aba c”你需要修改的次数。但是，我们可以看到由子串“abba”变为“aba”只需要一步。
为了得到子串的模糊匹配，我们将第一行设置为0。这表示我们不在乎匹配开始前在匹配对象中跳过的步数。
在最后一行，我们选取的不是右下角的数值，而是该行的最小值，这表示我们不在乎匹配结束后在匹配对象中跳过的步数。
我们选取最后一行的最小值，所以在此例中为1，这正是我们应该得到的值。
以下是这个算法的python实现：
def fuzzy_substring(needle, haystack):
"""Calculates the fuzzy match of needle inhaystack,
using a modified version of the Levenshtein distance
algorithm.
The function is modified from the levenshtein function
in the bktree module by Adam Hupp"""
m, n = len(needle), len(haystack)
# base cases
if m == 1:
return not needle in haystack
if not n:
return m
row1 = [0] * (n+1)
for i in range(0,m):
row2 = [i+1]
for j in range(0,n):
cost = ( needle[i] != haystack[j] )
row2.append(min(row1[j+1]+1, # deletion
row2[j]+1, #insertion
row1[j]+cost) #substitution
)
row1 = row2
return min(row1)