字符串匹配核心是快速定位子串，算法差异在于跳过无效比较的策略：暴力法逐位硬比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免费学习笔记（深入）”；
比如模式 “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 的重复子串