深入解析nryoung/algorithms中的KMP字符串搜索算法

什么是KMP算法

KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，由Donald Knuth、Vaughan Pratt和James H. Morris三位计算机科学家于1977年联合发表。该算法通过利用模式字符串本身的特性来避免不必要的比较，从而显著提高搜索效率。

算法核心思想

KMP算法的核心在于当出现不匹配时，能够利用已经匹配的部分信息，跳过一些肯定不会匹配的位置，避免回溯主串指针。这种特性使得KMP算法的时间复杂度可以达到O(n+m)，其中n是主串长度，m是模式串长度。

算法实现解析

nryoung/algorithms项目中的KMP实现包含两个主要函数：

1. compute_prefix函数

这个函数计算模式字符串的"部分匹配表"（也称为失败函数或前缀函数），这是KMP算法的关键预处理步骤：

def compute_prefix(word):
    word_length = len(word)
    prefix = [0] * word_length
    k = 0

    for q in range(1, word_length):
        while k > 0 and word[k] != word[q]:
            k = prefix[k - 1]

        if word[k + 1] == word[q]:
            k = k + 1
        prefix[q] = k
    return prefix

部分匹配表记录了模式字符串中每个位置的最长相同前后缀长度。这个表告诉我们在匹配失败时，模式字符串应该向右移动多少位。

2. search函数

这是KMP算法的主搜索函数：

def search(string, word):
    word_length = len(word)
    string_length = len(string)
    offsets = []

    if word_length > string_length:
        return offsets

    prefix = compute_prefix(word)
    q = 0
    for index, letter in enumerate(string):
        while q > 0 and word[q] != letter:
            q = prefix[q - 1]
        if word[q] == letter:
            q += 1
        if q == word_length:
            offsets.append(index - word_length + 1)
            q = prefix[q - 1]
    return offsets

该函数首先计算模式字符串的部分匹配表，然后遍历主串进行匹配。当出现不匹配时，利用部分匹配表调整模式字符串的位置，而不是简单地将主串指针回溯。

算法优势

1. 时间复杂度低：KMP算法的时间复杂度为O(n+m)，远优于朴素算法的O(n×m)
2. 无需回溯主串指针：主串指针只向前移动，不会回溯
3. 预处理信息可复用：对于同一个模式串，部分匹配表只需计算一次

实际应用场景

KMP算法特别适用于以下场景：

• 在长文本中搜索固定模式
• 需要多次搜索同一个模式串
• 处理DNA序列匹配等生物信息学问题
• 文本编辑器的查找功能实现

算法改进与变种

基于KMP算法，研究者们还发展出了多种改进算法，如：

• Boyer-Moore算法：从右向左比较模式串
• Sunday算法：利用出现不匹配时主串中下一个字符的信息
• AC自动机：多模式串匹配的扩展

总结

nryoung/algorithms项目中的KMP实现简洁高效，完整展示了这一经典字符串匹配算法的核心思想。通过理解部分匹配表的构建和利用方式，我们可以更好地掌握KMP算法的精髓，并将其应用到实际的字符串处理问题中。