实现字符串匹配函数

题目

实现字符串匹配函数

信息

• 类型：问答
• 难度：⭐

考点

暴力匹配算法,字符串遍历,边界条件处理

快速回答

实现字符串匹配的暴力算法（Brute Force）步骤如下：

• 使用两层循环遍历主串和模式串
• 外层循环遍历主串每个起始位置（0 到 n-m）
• 内层循环逐个比较主串和模式串的字符
• 全部字符匹配时返回起始位置
• 未找到匹配返回 -1

时间复杂度：O(n*m)，其中 n 是主串长度，m 是模式串长度。

解析

原理说明

暴力匹配（Brute Force）是最基础的字符串匹配算法，核心思想是：从主串的每个可能位置开始，逐个与模式串字符比较。具体步骤：

1. 设主串为 haystack，模式串为 needle
2. 遍历 haystack 的每个起始位置 i（0 ≤ i ≤ n-m）
3. 对于每个 i，比较 haystack[i+j] 和 needle[j]（0 ≤ j < m）
4. 若所有字符匹配则返回 i
5. 若出现不匹配则跳出内层循环，i 移动到下一个位置

代码示例

def strStr(haystack: str, needle: str) -> int:
    n, m = len(haystack), len(needle)
    if m == 0:  # 空模式串处理
        return 0

    for i in range(n - m + 1):  # 遍历所有有效起始位置
        for j in range(m):
            if haystack[i+j] != needle[j]:
                break
            if j == m - 1:  # 全部字符匹配
                return i
    return -1  # 未找到匹配

最佳实践

• 边界处理：检查模式串为空时直接返回0（约定空串是任何串的子串）
• 提前终止：主串剩余长度不足时立即终止外层循环（i ≤ n-m）
• 短路优化：内层循环发现不匹配立即跳出，减少不必要的比较

常见错误

• 索引越界：未检查主串剩余长度导致 haystack[i+j] 越界（正确做法：外层循环条件 i ≤ n-m）
• 空串处理：未处理 needle 为空串的情况（应返回0）
• 遗漏匹配：内层循环结束后未检查是否完全匹配（需判断 j == m-1）

扩展知识

• KMP算法：利用部分匹配表跳过不必要的比较，时间复杂度 O(n+m)
• Boyer-Moore算法：从右向左比较模式串，利用坏字符和好后缀规则跳跃
• Rabin-Karp算法：基于哈希的匹配，通过滚动哈希快速比较子串
• 应用场景：文本编辑器查找、生物信息学DNA序列匹配、防抄袭检测等

暴力匹配虽简单，但实际工程中更常用高效算法（如Python的find()方法底层通常使用Boyer-Moore）。理解暴力匹配是学习高级算法的基础。