KMP

KMP算法，全称Knuth-Morris-Pratt字符串搜索算法，是一种高效的字符串搜索（或模式匹配）算法。它由Donald Knuth、Vaughan Pratt和James H. Morris共同发明，能够快速地在一个文本串（text）中查找一个模式串（pattern），特别是在模式串较长或在一个文本串中多次查找时。

KMP算法的特点：

1. 单次预处理：KMP算法首先对模式串进行一次预处理，构建一个部分匹配表（也称为"前缀函数"或"失配表"），用于在搜索过程中遇到不匹配的情况时确定下一步的搜索位置。
2. 线性时间复杂度：在最坏的情况下，KMP算法的时间复杂度为O(n+m)，其中n是文本串的长度，m是模式串的长度。
3. 无回溯：与简单的回溯字符串搜索算法（如朴素算法）不同，KMP算法不会在文本串中来回移动，因此效率更高。

KMP算法的基本步骤：

1. 预处理模式串：构建部分匹配表。
2. 搜索：使用部分匹配表在文本串中搜索模式串。

代码使用示例：

以下是KMP算法的一个简单Python实现：

def kmp_search(text, pattern):
    # 预处理模式串，构建部分匹配表
    def compute_lps(pattern):
        length = 0  # length of the previous longest prefix suffix
        lps = [0] * len(pattern)  # lps[0] is always 0
        i = 1
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps

    lps = compute_lps(pattern)
    i = j = 0  # i是text的索引，j是pattern的索引
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == len(pattern):
            print(f"Pattern found at index {i - j}")
            j = lps[j - 1]  # 继续搜索下一次出现
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]  # 根据部分匹配表移动j
            else:
                i += 1

# 示例使用
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_search(text, pattern)