python 模糊匹配KMP 算法 案例

KMP算法是一种字符串匹配算法，可以实现模糊匹配。在python中实现KMP算法可以参考以下代码：

def kmp_search(pattern, text):
    m = len(pattern)
    n = len(text)
    lps = compute_lps_array(pattern, m)
    i = 0 # index for text[]
    j = 0 # index for pattern[]
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            print("Found pattern at index " + str(i-j))
            j = lps[j-1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1

def compute_lps_array(pattern, m):
    lps = [0]*m
    len = 0
    i = 1
    while i < m:
        if pattern[i]== pattern[len]:
            len += 1
            lps[i] = len
            i += 1
        else:
            if len != 0:
                len = lps[len-1]
            else:
                lps[i] = 0
                i += 1
    return lps

上述代码中，kmp_search函数用于进行模糊匹配，参数pattern表示模式串，参数text表示待匹配的文本串。compute_lps_array函数用于计算最长前缀后缀匹配数组，它的参数pattern表示模式串，参数m表示模式串的长度。

下面是一个案例，假设我们需要在文本串中查找模式串"ABC"出现的位置：

text = "ABABDABACDABABCABAB"
pattern = "ABC"
kmp_search(pattern, text)

输出结果为：

Found pattern at index 10
Found pattern at index 19

说明模式串"ABC"在文本串中分别出现在位置10和位置19。