KMP算法（字符串匹配）

题目描述
给定一个文本串text和一个模式串pattern，请你在text中找出pattern第一次出现的起始位置。如果pattern不是text的子串，则返回-1。

核心概念

• 文本串：待搜索的长字符串
• 模式串：要匹配的短字符串
• 前缀：包含首字母但不包含尾字母的连续子串
• 后缀：包含尾字母但不包含首字母的连续子串

暴力解法的问题
传统的暴力匹配需要回溯文本串指针，时间复杂度为O(m×n)：

def brute_force(text, pattern):
    m, n = len(text), len(pattern)
    for i in range(m - n + 1):
        j = 0
        while j < n and text[i+j] == pattern[j]:
            j += 1
        if j == n:
            return i
    return -1

KMP核心思想
利用已匹配的信息，避免文本串指针的回溯。当出现不匹配时，模式串向右滑动到合适位置继续匹配。

关键步骤详解

步骤1：构建next数组
next数组存储模式串每个位置的最长相等前后缀长度：

1. 初始化next[0] = 0，i = 1，j = 0
2. 遍历模式串(i从1到n-1)：
   • 当pattern[i] != pattern[j]且j > 0时，j = next[j-1]（回退）
   • 当pattern[i] == pattern[j]时，j += 1
   • next[i] = j

示例：pattern = "ABABC"

• i=1, j=0: 'B'≠'A' → next[1]=0
• i=2, j=0: 'A'='A' → j=1 → next[2]=1
• i=3, j=1: 'B'='B' → j=2 → next[3]=2
• i=4, j=2: 'C'≠'A' → j=next[1]=0 → 'C'≠'A' → next[4]=0

最终next = [0,0,1,2,0]

步骤2：利用next数组进行匹配

1. 初始化i=0（文本串指针），j=0（模式串指针）
2. 遍历文本串：
   • 当text[i] == pattern[j]时，双指针同时右移
   • 当不匹配且j>0时，j = next[j-1]（模式串滑动）
   • 当不匹配且j=0时，只移动文本串指针
3. 当j == n时，返回i - n

完整代码实现

def kmp_search(text, pattern):
    if not pattern:
        return 0
    
    # 构建next数组
    def build_next(p):
        next_arr = [0] * len(p)
        j = 0
        for i in range(1, len(p)):
            while j > 0 and p[i] != p[j]:
                j = next_arr[j-1]
            if p[i] == p[j]:
                j += 1
            next_arr[i] = j
        return next_arr
    
    next_arr = build_next(pattern)
    j = 0
    
    # 开始搜索
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = next_arr[j-1]
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            return i - j + 1
    
    return -1

复杂度分析

• 时间复杂度：O(m+n)，其中m是文本串长度，n是模式串长度
• 空间复杂度：O(n)，用于存储next数组

实际应用示例
text = "ABABABCABAB", pattern = "ABABC"
匹配过程：

1. 前4个字符"ABAB"匹配成功
2. 第5个字符' '≠'C'，j回退到next[3]=2
3. 从"ABA"开始继续匹配，最终找到完整匹配

KMP算法通过预处理模式串，实现了高效的字符串匹配，是许多文本编辑器和搜索引擎的基础算法。