字符串匹配核心是快速定位子串，算法差异在于跳过无效比较的策略：暴力法逐位硬比O(n×m)；KMP用next数组避免回溯O(n+m)；BM从后往前依坏字符/好后缀规则跳跃；RK用哈希预筛再校验，平均O(n+m)。

Python字符串匹配，核心是“在一段文本里快速定位某个子串的位置”。不同算法的差别，主要体现在“怎么跳过无效比较”上——越少比、越快跳，效率越高。

暴力匹配：一个位置一个位置试

最直白的做法：从文本开头起，每挪一位就拿整个模式串去硬对一遍。比如文本是"ababcababa"，模式是"aba"，就依次检查"aba"、"bab"、"abc"……直到某次完全吻合。

优点是好懂、不用预处理；缺点是重复劳动多——前面已比过"ab"，下一位又从头比"ba"，没利用已有信息。

• 时间复杂度固定为 O(n×m)，n 是文本长，m 是模式长
• 适合短文本或一次性查找，不常用于性能敏感场景

KMP算法：靠“最长公共前后缀”跳步

KMP 的关键在于预处理模式串，生成一个 next 数组（也叫 π 表）。它记录：当在第 j 位失配时，模式串能整体往前滑多少位，而不漏掉可能的匹配。

立即学习“Python免费学习笔记（深入）”；

macOS UI 自动化技能包 —— 用 Python 控制你的 Mac

让 macOS 自动化像说话一样简单 —— 用代码控制你的 Mac，无需学习 AppleScript 系统要求 macOS 14+ (Sonoma) Python 3.9+ 需要开启：辅助功能 + 屏幕录制权限

下载

比如模式 "ABABAC"，它的 next 是 [0,0,0,1,2,0]。遇到失配，不回退文本指针，而是把模式串的起点挪到 next[j−1] 对应位置继续比。

• 避免了文本指针回溯，单次扫描完成匹配
• 预处理 O(m)，搜索 O(n)，总时间 O(n+m)
• 空间开销 O(m)，适合模式串固定、多次搜索的场景

Boyer-Moore：从后往前，大胆跳过

它不按常规从左到右，而是先比模式串末尾字符。一旦失配，根据两个规则决定跳多远：

• 坏字符规则：看失配处文本字符在模式串里最后出现的位置，据此右移
• 好后缀规则：看已成功匹配的后缀，在模式中是否还存在相同子串，决定最小安全位移

实际中常只用坏字符规则简化实现，平均性能极佳，尤其适合模式较长、字母表有限（如英文）的情况。

Rabin-Karp：用哈希“预筛”，再精判

把模式串和每个等长文本子串都算一个哈希值。如果哈希不同，直接跳过；只有哈希相同时，才逐字符确认是否真匹配。

本质是用数值比较代替字符串比较，大幅降低平均比较次数。但要注意哈希冲突——两个不同字符串算出同一哈希值，得靠二次校验兜底。

• 平均时间 O(n+m)，最坏仍 O(n×m)
• 天然支持多模式匹配（如同时找多个关键词）
• 适合需要滚动计算的场景，比如查找所有长度为 m 的重复子串