文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载导读本文以 algorithm-base 仓库《字符串匹配算法》一文为核心骨架系统讲解字符串匹配的定义、BFBrute Force暴力匹配、BMBoyer-Moore坏字符与好后缀规则、KMP 最长公共前后缀与 next 数组三大算法的完整推导过程并给出全部 Java / Python 双语言实现。读者学完本文后不仅能手写三种算法并熟练 AC LeetCode 28「实现 strStr()」还能透彻理解移动位数与主串无关、只与模式串有关这一贯穿 BM 与 KMP 的核心思想。从一个生活场景认识字符串匹配故事从一家菜馆说起皇上生辰袁记菜馆被选为庆典菜品供应方。皇上按菜单点了 666 道菜但做西湖醋鱼的师傅请假回家了——万一皇上点了这道菜菜馆可就完了。店小二们反复核对最终确认菜单里没有西湖醋鱼大家才松了一口气。这个故事背后就是一个字符串匹配问题在一长串菜单主串中查找是否包含西湖醋鱼模式串这道菜。形式化定义设 S 和 T 是给定的两个串在主串 S 中找到模式串 T 的过程称为字符串匹配。如果在主串 S 中找到模式串 T则称匹配成功函数返回 T 在 S 中首次出现的位置否则匹配不成功返回 -1。举例主串 S abcabaabcabac模式串 T baabT 第一次在 S 中出现的位置下标为 4字符串首字符下标为 0因此返回 4。若模式串没有出现在主串中则返回 -1。本仓库README.md将字符串匹配单独列为一个系列包含 BF算法.md、BM.md、KMP.md 三篇独立文档与本文相呼应。下文按暴力 → 加速 → 线性的演进脉络逐一展开。一、BF 算法Brute Force暴力匹配1.1 算法思想BF 算法是最直观的匹配方式核心只有一句话将模式串与主串逐字符对齐比较一致时继续比较下一字符直到比较完整个模式串不一致时将模式串整体后移一位重新从模式串首位开始对比重复以上步骤。举例而言主串 S abcabaabcabac模式串 T baab。第一次尝试把 T 对齐到 S 的 0 号位首字符b与a不等后移一位对齐到 1 号位b与b相等继续比较……直到对齐到 4 号位时baab与abaaS[4..7]完全一致匹配成功。该过程在原文档中配有动画演示。1.2 经典题目LeetCode 28. 实现 strStr()题目描述给定一个 haystack 字符串和一个 needle 字符串在 haystack 字符串中找出 needle 字符串出现的第一个位置从 0 开始。如果不存在则返回 -1。示例 1输入: haystack hello, needle ll 输出: 2示例 2输入: haystack aaaaa, needle bba 输出: -1题目解析题目本身不难但需要格外注意两个边界情况模式串长度为 0时应返回什么按题目惯例返回 0模式串长度大于主串长度时主串里不可能出现模式串直接返回 -1。这两点正是许多实现看着对却 AC 不了的常见原因。题目代码朴素双循环版class Solution { public int strStr(String haystack, String needle) { int haylen haystack.length(); int needlen needle.length(); //特殊情况 if (haylen needlen) { return -1; } if (needlen 0) { return 0; } //主串 for (int i 0; i haylen - needlen 1; i) { int j; //模式串 for (j 0; j needlen; j) { //不符合的情况直接跳出主串指针后移一位 if (haystack.charAt(ij) ! needle.charAt(j)) { break; } } //匹配成功 if (j needlen) { return i; } } return -1; } }from typing import List class Solution: def strStr(self, haystack: str, needle: str)-int: haylen len(haystack) needlen len(needle) # 特殊情况 if haylen needlen: return -1 if needlen 0: return 0 # 主串 for i in range(0, haylen - needlen 1): # 模式串 j 0 while j needlen: if haystack[i j] ! needle[j]: break j 1 # 匹配成功 if j needlen: return i return -11.3 BF 算法的另一种写法显式回退原理与朴素版完全一致只是用两个独立指针 i、j 分别指向主串与模式串把模式串整体后移改写为j 归零、i 回退到本次匹配起点 1。这也是不少教科书上的写法class Solution { public int strStr(String haystack, String needle) { //i代表主串指针j模式串 int i,j; //主串长度和模式串长度 int halen haystack.length(); int nelen needle.length(); //循环条件这里只有 i 增长 for (i 0 , j 0; i halen j nelen; i) { //相同时则移动 j 指针 if (haystack.charAt(i) needle.charAt(j)) { j; } else { //不匹配时将 j 重新指向模式串的头部将 i 本次匹配的开始位置的下一字符 i - j; j 0; } } //查询成功时返回索引查询失败时返回 -1 int renum j nelen ? i - nelen : -1; return renum; } }from typing import List class Solution: def strStr(self, haystack: str, needle: str)-int: # i代表主串指针j模式串 i 0 j 0 # 主串长度和模式串长度 halen len(haystack) nelen len(needle) # 循环条件这里只有 i 增长 while i halen and j nelen: # 相同时则移动 j 指针 if haystack[i] needle[j]: j 1 else: # 不匹配时将 j 重新指向模式串的头部将 i 本次匹配的开始位置的下一字符 i - j j 0 i 1 # 查询成功时返回索引查询失败时返回 -1 renum i - nelen if j nelen else -1 return renum复杂度直觉从两层循环结构可以看出BF 算法最坏情况下需要对主串的每个位置都尝试一轮模式串比较时间复杂度为 O(n × m)n 为主串长度m 为模式串长度。它的低效点在于一次失配后只后移一位白白丢弃了大量已比较过的信息。二、BM 算法Boyer-Moore2.1 BF 的缺陷在哪里假设主串中有一长段与模式串高度相似的内容例如模式串 T abcdex。用 BF 匹配时第一次比较abcde全部成功、只有最后一个字符x失败因为模式串中每个字符都不相同此时完全没必要让模式串一位一位地右移、把abcde反复重比——可以直接跳过若干步骤。问题在于跳多少依据什么跳BM 算法的回答是从后往前比较并依据坏字符与好后缀两条规则计算滑动距离。2.2 坏字符规则Bad CharacterBM 算法从模式串的末尾开始向前比较。当发现第一个不匹配的字符时主串中这个字符被称为坏字符。根据坏字符在模式串中的出现情况分三种处理模式串中没有坏字符直接把模式串右移到坏字符的后面一位即可。例如坏字符为 f模式串中完全没有 ff 不可能与模式串任何字符匹配成功直接跳过整段模式串中存在一个坏字符将模式串中该字符与主串坏字符对齐继续从右往左比较模式串中存在多个坏字符此时必须让最靠右的那个对应字符与坏字符对齐。为什么必须取最靠右的原文档用一个反例说明了后果如果不按此规则而让左边的重复字符去对齐就会漏掉真正的匹配——主串中明明含有babac这样的合法子串却会匹配失败。所以坏字符规则的正确表述是让模式串中最靠右的对应字符与坏字符相对。据此可以总结坏字符情况下的移动位数计算方式给字符加上下标后坏字符位置模式串中的下标记为 j找到坏字符在模式串中最靠右的出现位置下标移动位数 j - 该最靠右下标模式串中没有该字符时按 -1 处理。一个隐蔽的 Bug在某些情况下坏字符在模式串最靠右的位置可能出现在坏字符的右边即匹配位置右侧此时计算出的移动位数会是负数模式串不但不右移反而可能左移——这显然是错误的。BM 算法解决这个问题的思路是引入第二条规则好后缀让两条规则互相兜底。2.3 好后缀规则Good SuffixBM 从右往左比较发现坏字符时坏字符右侧已经匹配成功的部分就是好后缀。例如某次比较中cac已经匹配成功在红色阴影处发现坏字符此时cac就是好后缀。规则拿好后缀去模式串中查找如果找到另一个与好后缀相匹配的串就把模式串滑动到该串与好后缀对齐的位置。对好后缀规则原文档给出了三条重要的总结如果模式串含有好后缀无论是中间还是头部都可以按规则移动如果好后缀在模式串中出现多次则以最右侧的好后缀为基准如果模式串头部含有好后缀的子串则可以按规则移动但中间部分含有好后缀子串则不可以因为只有头部的前缀才能安全承接失配位置左侧已匹配的部分如果在模式串尾部就出现不匹配即根本不存在好后缀时则退化为根据坏字符进行移动。这一点许多资料没有提到是容易踩坑的细节其依据出自 BM 算法的原始论文Boyer R SMoore J S. A fast string searching algorithm. Communications of the ACM, 1977, 10: 762-772。最终移动策略分别计算坏字符和好后缀两种规则下的滑动位数好后缀存在的情况然后取两者中的最大值作为模式串的最终滑动位数。取最大值既能保证不出现坏字符规则下的左移倒退又能让滑动尽量快。2.4 BM 完整实现Java / PythonBM 代码相对较长但其结构非常清晰badChar预处理坏字符移动表、goodSuffix预处理好后缀表、move计算好后缀移动位数、bm主循环从后往前扫描。原文档中的代码均在 LeetCode 28 上 AC可放心食用class Solution { public int strStr(String haystack, String needle) { char[] hay haystack.toCharArray(); char[] need needle.toCharArray(); int haylen haystack.length(); int needlen need.length; return bm(hay,haylen,need,needlen); } //用来求坏字符情况下移动位数 private static void badChar(char[] b, int m, int[] bc) { //初始化 for (int i 0; i 256; i) { bc[i] -1; } //m 代表模式串的长度如果有两个 a,则后面那个会覆盖前面那个 for (int i 0; i m; i) { int ascii (int)b[i]; bc[ascii] i;//下标 } } //用来求好后缀条件下的移动位数 private static void goodSuffix (char[] b, int m, int[] suffix,boolean[] prefix) { //初始化 for (int i 0; i m; i) { suffix[i] -1; prefix[i] false; } for (int i 0; i m - 1; i) { int j i; int k 0; while (j 0 b[j] b[m-1-k]) { --j; k; suffix[k] j 1; } if (j -1) prefix[k] true; } } public static int bm (char[] a, int n, char[] b, int m) { int[] bc new int[256];//创建一个数组用来保存最右边字符的下标 badChar(b,m,bc); //用来保存各种长度好后缀的最右位置的数组 int[] suffix_index new int[m]; //判断是否是头部如果是头部则true boolean[] ispre new boolean[m]; goodSuffix(b,m,suffix_index,ispre); int i 0;//第一个匹配字符 //注意结束条件 while (i n-m) { int j; //从后往前匹配匹配失败找到坏字符 for (j m - 1; j 0; --j) { if (a[ij] ! b[j]) break; } //模式串遍历完毕匹配成功 if (j 0) { return i; } //下面为匹配失败时如何处理 //求出坏字符规则下移动的位数就是我们坏字符下标减最右边的下标 int x j - bc[(int)a[ij]]; int y 0; //好后缀情况求出好后缀情况下的移动位数,如果不含有好后缀的话则按照坏字符来 if (y m-1 m - 1 - j 0) { y move(j, m, suffix_index,ispre); } //移动 i i Math.max(x,y); } return -1; } // j代表坏字符的下标 private static int move (int j, int m, int[] suffix_index, boolean[] ispre) { //好后缀长度 int k m - 1 - j; //如果含有长度为 k 的好后缀返回移动位数 if (suffix_index[k] ! -1) return j - suffix_index[k] 1; //找头部为好后缀子串的最大长度从长度最大的子串开始 for (int r j 2; r m-1; r) { //如果是头部 if (ispre[m-r] true) { return r; } } //如果没有发现好后缀匹配的串或者头部为好后缀子串则移动到 m 位也就是匹配串的长度 return m; } }from typing import List class Solution: def strStr(self, haystack: str, needle: str)-int: haylen len(haystack) needlen len(needle) return self.bm(haystack, haylen, needle, needlen) # 用来求坏字符情况下移动位数 def badChar(self, b: str, m: int, bc: List[int]): # 初始化 for i in range(0, 256): bc[i] -1 # m 代表模式串的长度如果有两个 a则后面那个会覆盖前面那个 for i in range(0, m,): ascii ord(b[i]) bc[ascii] i# 下标 # 用来求好后缀条件下的移动位数 def goodSuffix(self, b: str, m: int, suffix: List[int], prefix: List[bool]): # 初始化 for i in range(0, m): suffix[i] -1 prefix[i] False for i in range(0, m - 1): j i k 0 while j 0 and b[j] b[m - 1 - k]: j - 1 k 1 suffix[k] j 1 if j -1: prefix[k] True def bm(self, a: str, n: int, b: str, m: int)-int: bc [0] * 256# 创建一个数组用来保存最右边字符的下标 self.badChar(b, m, bc) # 用来保存各种长度好后缀的最右位置的数组 suffix_index [0] * m # 判断是否是头部如果是头部则True ispre [False] * m self.goodSuffix(b, m, suffix_index, ispre) i 0# 第一个匹配字符 # 注意结束条件 while i n - m: # 从后往前匹配匹配失败找到坏字符 j m - 1 while j 0: if a[i j] ! b[j]: break j - 1 # 模式串遍历完毕匹配成功 if j 0: return i # 下面为匹配失败时如何处理 # 求出坏字符规则下移动的位数就是我们坏字符下标减最右边的下标 x j - bc[ord(a[i j])] y 0 # 好后缀情况求出好后缀情况下的移动位数,如果不含有好后缀的话则按照坏字符来 if y m - 1 and m - 1 - j 0: y self.move(j, m, suffix_index, ispre) # 移动 i max(x, y) return -1 # j代表坏字符的下标 def move(j: int, m: int, suffix_index: List[int], ispre: List[bool])-int: # 好后缀长度 k m - 1 - j # 如果含有长度为 k 的好后缀返回移动位数 if suffix_index[k] ! -1: return j - suffix_index[k] 1 # 找头部为好后缀子串的最大长度从长度最大的子串开始 for r in range(j 2, m): # //如果是头部 if ispre[m - r] True: return r # 如果没有发现好后缀匹配的串或者头部为好后缀子串则移动到 m 位也就是匹配串的长度 return m2.5 理解核心两张预计算表BM 代码中最关键的一点是两种规则的移动位数只与模式串有关与主串无关因此可以在匹配开始前一次性预计算并存入数组匹配时 O(1) 查表数组长度含义预处理位置bc256每个 ASCII 字符在模式串中最靠右的下标初始化为 -1正因后覆盖前才天然得到最靠右位置BM.md 中badCharsuffix_indexm各种长度的好后缀在模式串中的最右起始位置初始化为 -1goodSuffixisprem长度为 k 的后缀是否同时也是模式串的头部前缀goodSuffix其中suffix_index[k] ! -1对应好后缀规则的结论 1模式串内部含有好后缀ispre[m-r] true对应结论 2头部含有好后缀子串最终return m对应结论 3既不含有好后缀、头部也没有匹配子串时直接滑动整个模式串长度。三条规则与三处代码分支一一对应理解这张表就能彻底读懂 BM 主循环。三、KMP 算法Knuth-Morris-Pratt3.1 KMP 与 BM 的本质相通KMP 是考研与面试的必考算法。实际上BM 和 KMP 的本质是一样的都是利用失配时已匹配部分的信息来避免主串指针回退。理解了 BM 的移动只取决于模式串之后再来理解 KMP 会轻松很多。为便于理解原文档将指针移动改述为模式串移动——两者相对于主串的运动是一致的重新比较时都是接着上次的位置继续。3.2 核心概念最长公共前后缀KMP 的难点不在匹配过程而在如何计算移动距离。假设在某位置匹配失败红色阴影处失配、绿色部分匹配成功此时观察匹配成功的部分它的所有前缀中能与同样长度的后缀相等的最长那一个就是最长公共前后缀。失配时模式串可以安全地滑动到最长公共前后缀对齐的位置——因为此前缀已经与主串尾部匹配过无需重比。3.3 next 数组存什么、怎么用既然移动位数只与模式串有关KMP 也像 BM 一样预计算一张表这张表就是next 数组。next 数组存的是最长公共前后缀中前缀的结尾字符下标。使用方式当主串指针 i 与模式串指针 j 失配时令j next[j-1] 1即把 j 跳转到最大公共前后缀前缀的后一位主串指针 i 不回退继续匹配。注意很多教科书的 next 数组定义例如存长度或前缀长度减一不一致理解语义即可代码以本仓库实现为准。3.4 KMP 完整实现Java / Pythonclass Solution { public int strStr(String haystack, String needle) { //两种特殊情况 if (needle.length() 0) { return 0; } if (haystack.length() 0) { return -1; } // char 数组 char[] hasyarr haystack.toCharArray(); char[] nearr needle.toCharArray(); //长度 int halen hasyarr.length; int nelen nearr.length; //返回下标 return kmp(hasyarr,halen,nearr,nelen); } public int kmp (char[] hasyarr, int halen, char[] nearr, int nelen) { //获取next 数组 int[] next next(nearr,nelen); int j 0; for (int i 0; i halen; i) { //发现不匹配的字符然后根据 next 数组移动指针移动到最大公共前后缀的 //前缀的后一位,和咱们移动模式串的含义相同 while (j 0 hasyarr[i] ! nearr[j]) { j next[j - 1] 1; //超出长度时可以直接返回不存在 if (nelen - j i halen) { return -1; } } //如果相同就将指针同时后移一下比较下个字符 if (hasyarr[i] nearr[j]) { j; } //遍历完整个模式串返回模式串的起点下标 if (j nelen) { return i - nelen 1; } } return -1; } //这一块比较难懂不想看的同学可以忽略了解大致含义即可或者自己调试一下看看运行情况 //我会每一步都写上注释 public int[] next (char[] needle,int len) { //定义 next 数组 int[] next new int[len]; // 初始化 next[0] -1; int k -1; for (int i 1; i len; i) { //我们此时知道了 [0,i-1]的最长前后缀但是k1的指向的值和i不相同时我们则需要回溯 //因为 next[k]就时用来记录子串的最长公共前后缀的尾坐标即长度 //就要找 k1前一个元素在next数组里的值,即next[k1] while (k ! -1 needle[k 1] ! needle[i]) { k next[k]; } // 相同情况就是 k的下一位和 i 相同时此时我们已经知道 [0,i-1]的最长前后缀 //然后 k 1 又和 i 相同最长前后缀加1即可 if (needle[k1] needle[i]) { k; } next[i] k; } return next; } }from typing import List class Solution: def strStr(self, haystack: str, needle: str)-int: # 两种特殊情况 if len(needle) 0: return 0 if len(haystack) 0: return -1 # 长度 halen len(haystack) nelen len(needle) # 返回下标 return self.kmp(haystack, halen, needle, nelen) def kmp(self, hasyarr: str, halen: int, nearr: str, nelen: int)-int: # 获取next 数组 next self.next(nearr, nelen) j 0 for i in range(0, halen): # 发现不匹配的字符然后根据 next 数组移动指针移动到最大公共前后缀的 # 前缀的后一位,和咱们移动模式串的含义相同 while j 0 and hasyarr[i] ! nearr[j]: j next[j - 1] 1 # 超出长度时可以直接返回不存在 if nelen - j i halen: return -1 # 如果相同就将指针同时后移一下比较下个字符 if hasyarr[i] nearr[j]: j 1 # 遍历完整个模式串返回模式串的起点下标 if j nelen: return i - nelen 1 return -1 # 这一块比较难懂不想看的同学可以忽略了解大致含义即可或者自己调试一下看看运行情况 # 我会每一步都写上注释 def next(self, needle: str, len:int)-List[int]: # 定义 next 数组 next [0] * len # 初始化 next[0] -1 k -1 for i in range(1, len): # 我们此时知道了 [0,i-1]的最长前后缀但是k1的指向的值和i不相同时我们则需要回溯 # 因为 next[k]就时用来记录子串的最长公共前后缀的尾坐标即长度 # 就要找 k1前一个元素在next数组里的值,即next[k1] while k ! -1 and needle[k 1] ! needle[i]: k next[k] # 相同情况就是 k的下一位和 i 相同时此时我们已经知道 [0,i-1]的最长前后缀 # 然后 k 1 又和 i 相同最长前后缀加1即可 if needle[k 1] needle[i]: k 1 next[i] k return next3.5 KMP 的复杂度与代码结构印证从代码结构可以清楚看到 KMP 的两个阶段next 预处理next函数单层 for 循环扫描模式串配合 while 回溯整体线性扫描一遍模式串主匹配kmp函数单层 for 循环扫描主串失配时 j 通过 next 数组回退但 i 永不回退。两层循环都没有发生模式串失配就整体重扫的行为因此 KMP 的整体时间复杂度可以达到 O(n m) 级别n 为主串长度m 为模式串长度——这是算法教科书公认的结论也与代码的单层扫描结构吻合。相比 BF 的 O(n × m) 最坏情况KMP 以空间换时间额外 O(m) 的 next 数组换来了匹配阶段的线性表现。四、三种算法横向对比与选型算法比较方向失配后如何处理关键预计算核心思想BF从前往后模式串后移一位从头重比无暴力枚举所有对齐位置BM从后往前取坏字符、好后缀两者移动位数中的较大值bc/suffix_index/ispre从后往前比较 跳跃式滑动KMP从前往后主串指针不回退模式串指针跳转到 next[j-1]1next最长公共前后缀复用已匹配信息三者共同点匹配过程中的移动距离只与模式串有关与主串无关因此都可以通过预计算表来加速。区别在于 BM 利用的是坏字符与好后缀两种启发信息、从后往前扫描平均表现好KMP 利用的是最长公共前后缀、从前往后扫描最坏情况有严格保证且思想更简单、更常出现在教材与考试中。五、在仓库中的定位与延伸学习本文内容出自 algorithm-base 仓库的 字符串匹配算法.md该仓库以动画模拟的方式讲解数据结构与算法其字符串匹配系列还包括三篇独立详解可与本文对照阅读BF算法.mdBF 算法与 LeetCode 28 的完整推导BM.md坏字符、好后缀规则的图例讲解KMP.md最长公共前后缀与 next 数组的图例讲解。另外做字符串匹配相关题目时常用的 API 可参考仓库的 Leetcode常用类和函数.md其中整理了charAt(i)按索引取字符、indexOf查找子串首次出现位置找不到返回 -1、toCharArray()字符串转字符数组等常用函数——比如 KMP 代码中反复用到的haystack.charAt(i)与toCharArray()就来自这些基础操作。刷题前花几分钟熟悉这些 API可以显著提升编码效率。小结从 BF 的暴力枚举到 BM 的坏字符 好后缀双规则跳跃再到 KMP 的 next 数组线性匹配三者的演进本质上是在回答同一个问题——失配之后怎样滑动才既不错过答案、又尽量少做无用功。理解了三张预计算表BM 的bc/suffix_index/ispre与 KMP 的next你就掌握了现代字符串匹配算法最核心的设计范式而 LeetCode 28 的双语言 AC 代码则足以支撑你在面试中快速写出可靠实现。赞分享文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载相关推荐如何快速构建现代化桌面应用WPF UI框架终极指南如何快速构建现代化桌面应用WPF UI框架终极指南 你是否还在为WPF应用的陈旧界面而烦恼想要让传统桌面应用拥有现代流畅的设计体验却又不想重写整个代码库UI组件桌面应用open-source-course社区建设指南如何打造活跃的开源学习社区open source course社区建设指南如何打造活跃的开源学习社区 open source courseGitHub 加速计划是一个专注于开源学习字符串匹配算法大全CLRS中KMP、BM、RK算法对比分析字符串匹配算法大全CLRS中KMP、BM、RK算法对比分析 在计算机科学中 字符串匹配算法 是解决文本搜索问题的核心技术。无论是文本编辑器中的查找功能、搜索文档教程示例工程上一篇Wand-Enhancer3 步免费解锁 WeMod Pro还能手机远程控游戏下一篇快速上手 authentik3 步搭好可自托管的身份认证与 SSO 中心创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考