做后端开发这些年我面过不少人也被面过很多次。LeetCode 009这道“找出字符串中第一个匹配项的下标”是我眼里最有意思的“简单题”之一。论难度暴力解法十分钟能写完可一旦面试官追问“能不能优化到O(n)”很多人当场就卡住了。字符串匹配这个看似朴素的需求背后是KMP、Rabin-Karp、Boyer-Moore这一整片算法森林而这道题正好是进入这片森林的入口。所以别看它标着“简单”真正把它吃透的人并不多。1. 题目到底在考什么一个“简单题”背后的三重门1.1 题目描述与本质拆解题目原文很直白给你两个字符串haystack主串和 needle模式串在主串中找出模式串第一个匹配项的下标从0开始计数如果模式串不是主串的一部分返回 -1。这其实就是C语言里strStr函数的翻版也是Java中String.indexOf()要做的事Python里则是str.find()。这个题本质上是子串查找问题。很多人看到“简单题”三个字以为就是遍历一下、比一比、找到了就返回确实没错。但往深处想子串查找是所有字符串处理的基础。文本编辑器里的CtrlF、日志系统里搜关键字、搜索引擎的短语匹配底层都要做这件事。如果只能靠暴力循环数据量一上去性能就崩了。1.2 三个隐藏考点这道简单题至少藏着三个考点很多人在面试时栽跟头就是因为只看到了第一层。第一个是边界条件处理。模式串为空时返回什么主串比模式串短时怎么办遍历时指针越界怎么处理这些细节看似琐碎却是考编码严谨度的试金石。LeetCode原题约定当needle为空字符串时返回0这一点和Java的indexOf行为一致但真到写代码时能主动处理的人少之又少。第二个是复杂度意识。暴力解法的时间复杂度是O(n×m)在数据规模大时完全不可接受。面试官往往不会满足于你写出暴力解而是会追问“还有没有更快的方案”。如果你脑子里没有KMP、Rabin-Karp这些概念这道“简单题”就会变成一票否决题。第三个是编码细节与变量管理。两层循环里索引怎么挪动、比较失败时怎么回退、找到匹配时下标怎么算这些都在考你对代码的掌控力。我见过不止一个候选人思路完全正确但写出来的循环边界就是差一个1最后调了十分钟也找不出错在哪。1.3 为什么它配得上“简单”标签LeetCode把难度标成Easy主要原因是暴力解法容易想到代码量小而且存在清晰的最优解。它不像动态规划那样需要建模也不像图论那样需要复杂的遍历策略。可也正因为简单它能在短时间内考察出面试者的思维深度——是把题目当“循环练习”草草做完还是会主动追问“我的解法是不是最优的”。2. 暴力解法从最朴素的思路开始2.1 思路与完整实现暴力解法的思路一句话就能说清在主串的每一个可能起始位置把模式串一个字符一个字符地比过去。如果完全匹配就返回这个起始下标所有位置都比完了没有匹配的就返回-1。以主串“hello”中找“ll”为例。从下标0开始h和l比不等下标1开始e和l比不等下标2开始l和l比相等继续比l和l比相等返回2。整个过程很符合人的直觉。public int strStr(String haystack, String needle) { int n haystack.length(), m needle.length(); if (m 0) return 0; for (int i 0; i n - m; i) { for (int j 0; j m; j) { if (haystack.charAt(i j) ! needle.charAt(j)) { break; } if (j m - 1) { return i; } } } return -1; }两个细节值得注意。一是外层循环的边界写成i n - m而不是i n。当主串剩下的长度已经不足模式串长度时后面不可能再匹配成功继续循环只会白白浪费时间。二是m 0时直接返回0这是题目约定也是工程上最自然的语义。2.2 最坏情况看似简单的代码也有性能陷阱暴力解法最坏情况是O(n×m)。什么时候会触发当主串和模式串存在大量重复前缀时。比如主串是“aaaaaaaaaaaaaaaaaaaaaaaaaab”模式串是“aaaaab”主串几乎全由a组成最后才有一个b。每次都从主串当前位置开始匹配每次都要比到模式串最后一个字符才失败然后主串指针只挪一格再次从头比较。数据量一大这种重复劳动是灾难级的。理解这个最坏情况很重要因为它直接引出了KMP算法存在的意义。暴力解法浪费在哪浪费在每次失配后只前进一格已经比较过的信息全部丢弃。如果主串和模式串前四个字符都匹配上了只是第五个字符失败那这“前四个字符匹配”的信息是很有价值的——能不能利用它让模式串直接多跳几步2.3 什么时候暴力解法就够用不是说一切都要KMP。实际工程里如果模式串很短比如3到5个字符或者被搜索的文本本身很小暴力解法的常数项极低反而可能比KMP更快。原因在于KMP需要提前构建next数组这个预处理也有成本模式串短时收益不明显。我自己的经验是当文本长度在几千字符以内、模式串长度小于10时直接暴力查找完全没问题。很多数据库和文本工具的查找功能在短模式场景下采用的也是朴素匹配的优化版本。所以别一上来就否定暴力解法先分析场景再选策略这是工程思维和算法竞赛思维的本质区别。3. KMP算法让主串指针永不回头的匹配3.1 核心思想空间换时间KMPKnuth-Morris-Pratt算法的革命性在于主串的指针永远不回溯。匹配失败时模式串向右滑动尽可能远的一段距离而不是像暴力解法那样只挪一格。这个“尽可能远”的距离是用预处理好的next数组算出来的空间复杂度只有O(m)。用一个生活化的例子帮大家建立直觉。你在书里查一个单词已经确认前五个字母都对上了第六个字母对不上。这时候你会翻回单词开头重新比吗不会。你会想这个单词的前三个字母和刚刚读过的后三个字母是不是一样的如果是那书里当前位置往前三个字母其实已经和单词开头对上了直接从第四个字母往后继续比就行。KMP干的就是这件事。3.2 next数组的本质最长相等前后缀next数组是KMP的魂也是很多人学了一半就放弃的坎。它的每个位置记录了模式串某个前缀子串的最长相等前后缀长度。一个概念先搞清楚前缀指除了最后一个字符以外、从开头开始的任意子串后缀指除了第一个字符以外、到结尾结束的任意子串。以“aabaa”为例它的前缀有a、aa、aab、aaba后缀有a、aa、baa、abaa。前后缀都含“a”和“aa”最长相等的是“aa”长度2。以我用得最多的口径来定义next[i]表示模式串needle[0..i]这个子串的最长相等前后缀长度。比如“aabaaf”这个模式串手推结果如下i子串最长相等前后缀next[i]0a无01aa“a”长度112aab无03aaba“a”长度114aabaa“aa”长度225aabaaf无0这个表就是KMP能跳的关键。当模式串在下标5处失配时因为前5个字符“aabaa”的最长相等前后缀长度是2说明主串当前位置之前的两个字符“aa”已经和模式串开头的“aa”对上了所以模式串直接从下标2继续比就行不用回到开头。3.3 构建next数组代码与逐步走读private int[] getNext(String needle) { int m needle.length(); int[] next new int[m]; int j 0; for (int i 1; i m; i) { while (j 0 needle.charAt(i) ! needle.charAt(j)) { j next[j - 1]; } if (needle.charAt(i) needle.charAt(j)) { j; } next[i] j; } return next; }这段代码很精炼但不好懂。变量j在这里表示“当前已经匹配上的前缀长度”也可以理解成“下一个要比对的前缀下标”。外层循环从i1开始因为next[0]恒为0。每轮循环要计算的是以当前字符结尾的最长相等前后缀长度。拿上面的“aabaaf”举例当i4时needle[4]是字符a此时j是2上一轮next[3]的值。比较needle[4]a和needle[2]b不相等于是j回退到next[1]1再比较needle[4]a和needle[1]a相等j变成2所以next[4]2。这里的核心是while循环里的j next[j - 1]。它做的事情和KMP匹配过程完全一致——如果当前字符和前缀的下一个字符对不上就继续看更短的前缀是否可能对上。很多初学者在这里写成j next[j]会直接导致死循环或者计算出错误结果这是KMP最容易错的地方之一。3.4 匹配过程与完整代码构建好next数组之后匹配过程就非常清爽了。主串从头走到尾i永远不回退模式串的j根据next数组来回跳。我们用一个完整例子来走一遍。主串haystack是“aabaabaaf”模式串needle是“aabaaf”上面已经算好next数组是[0,1,0,1,2,0]。匹配过程如下主串下标i主串字符动作j的变化0a与needle[0]a相等j11a与needle[1]a相等j22b与needle[2]b相等j33a与needle[3]a相等j44a与needle[4]a相等j55b与needle[5]f不等jnext[4]2再比b与needle[2]b相等j36a与needle[3]a相等j47a与needle[4]a相等j58f与needle[5]f相等j6等于m返回8-613最终返回3验证主串下标3到8确实是“aabaaf”。注意第5步——主串指针i停在5没有回退是靠j从5跳到2来实现模式串向右滑动的。这个滑动距离正是暴力解法浪费掉的那些重复比较。public int strStr(String haystack, String needle) { int n haystack.length(), m needle.length(); if (m 0) return 0; int[] next getNext(needle); int j 0; for (int i 0; i n; i) { while (j 0 haystack.charAt(i) ! needle.charAt(j)) { j next[j - 1]; } if (haystack.charAt(i) needle.charAt(j)) { j; } if (j m) { return i - m 1; } } return -1; }整个算法的时间复杂度是O(nm)。构建next数组消耗O(m)匹配过程消耗O(n)空间复杂度O(m)。3.5 KMP最容易踩的三个坑第一个坑是next数组口径混乱。网上教程有的是next[i]表示前i个子串的PMT值有的把next[0]设成-1然后整体后移代码形态都不一样。如果你按A教程掌握了理论又去抄B教程的代码很容易整个人懵掉。我建议固定一种口径next[i]表示第i个位置失配后应该跳回的位置即needle[0..i]的最长相等前后缀长度。代码里对应回退写next[j - 1]因为j是“已经匹配的长度”要前j个字符的最长相等前后缀对应的下标是j-1。第二个坑是数组越界。匹配循环里haystack.charAt(j)这个操作的前提是j小于m。什么时候会越界如果主串和模式串一路匹配到j等于m应该立即返回不用再取字符。所以每轮循环里if (j m)的判断要放在charAt(j)之前。顺序反了主串还没遍历完j就已经等于m再取needle.charAt(j)必然越界。第三个坑是把next数组的值当成移动距离。next[i]不是“模式串应该向右移动的格数”它是“模式串下标应该跳回的位置”。这两者的区别很微妙但直接决定了代码的写法。记住一点next数组给的是目标位置移动距离是j - next[j-1]由系统在循环中自然体现你不需要单独算。4. 面试与工程该不该直接调内置函数4.1 面试考场上为什么不能一句indexOf了事有些候选人看到这道题直接写一行return haystack.indexOf(needle);然后一脸得意。这确实能跑、结果也对但面试官想看的不是API调用而是你脑子里有没有算法。真到写业务代码当然该调库就调库但面试本质是能力考察——如果你对字符串匹配的理解只停在“调一个现成函数”那换一道没有内置函数可调的问题你是不是就没辙了比较稳的做法是分两步走。先写暴力解法明确说清楚复杂度然后主动提一句“我可以优化到O(n)用KMP”再把KMP写出来。这展示的不只是你会背代码而是你有复杂度意识、有方案对比意识、有工程选型意识。我面人的时候这两种回答的分差天壤之别。4.2 各语言内置查找的实现策略工程上成熟语言的内置查找函数都做了大量优化不是单纯的某种算法。Java的String.indexOf()会根据模式串长度和主串内容选择不同的策略短模式走朴素匹配的优化版长一点再考虑更复杂的方案。Python的str.find()底层也是混合策略CPython会在不同场景之间做切换。C语言的strstr()在不同标准库实现中甚至用过KMP和Boyer-Moore的变体。内置函数之所以“快”是因为它们能在运行时根据输入特征自适应地切换算法。但这不代表你不需要理解这些算法——恰恰相反只有理解了每种算法的适用场景你才知道为什么内置库要这么设计也才能在它们覆盖不了的场景里自己造轮子。4.3 工程中的选型建议如果在真实项目里手写字符串匹配我的建议是这样场景推荐方案理由文本短、模式短朴素匹配常数极小无需预处理文本长、模式中等KMP稳定O(nm)适合重复搜索模式很长、文本大Boyer-Moore实践中平均跳跃幅度大更快多个模式串同时匹配AC自动机在Trie上扩展KMP思想一次遍历匹配所有模式需要模糊匹配正则表达式引擎内部已经是编译过的状态机这个表是我做日志分析、敏感词过滤项目时实际用过的选型原则不是纸上谈兵。5. 其他匹配算法打开思路5.1 Rabin-Karp用哈希比较替代逐个字符Rabin-Karp的思路很巧妙把字符串当成一个进制数来算哈希值然后滑动窗口计算主串每个可能位置的哈希和模式串哈希比较。匹配两个字符串是否相等变成了比较两个整数是否相等速度飞快。public int strStr(String haystack, String needle) { int n haystack.length(), m needle.length(); if (m 0) return 0; long base 131L; long targetHash 0, curHash 0, power 1; for (int i 0; i m; i) { targetHash targetHash * base needle.charAt(i); curHash curHash * base haystack.charAt(i); power * base; } if (curHash targetHash check(haystack, 0, needle)) return 0; for (int i m; i n; i) { curHash curHash * base - haystack.charAt(i - m) * power haystack.charAt(i); if (curHash targetHash check(haystack, i - m 1, needle)) { return i - m 1; } } return -1; } private boolean check(String haystack, int start, String needle) { for (int i 0; i needle.length(); i) { if (haystack.charAt(start i) ! needle.charAt(i)) return false; } return true; }这段代码用了long防溢出但乘法仍然可能产生溢出。Rabin-Karp理论的复杂度是O(nm)但前提是哈希冲突足够少。实际应用中一旦哈希相等还需要二次确认代码里的check函数因为有可能两个不同字符串哈希值碰巧相同。这个算法还有个变体叫“滚动哈希”广泛用于去重和文本相似度检测但在单模式串匹配场景里它不一定比KMP更优因为预处理和每个位置计算哈希的常数开销不小。5.2 Boyer-Moore从右往左比跳得最远Boyer-Moore的思想更反直觉从模式串的最后一个字符开始往前比。模式串最后一个字符都匹配不上时就可以直接跳很大一段距离。它有两个规则坏字符规则和好后缀规则。坏字符规则举例模式串是“text”主串某个位置开始比较发现模式串最后一个字符t对应主串位置是字符x而x根本不在模式串里那模式串至少可以向右跳过一个模式串长度。因为x在模式串里没出现过主串的x不可能是任何可能匹配中的一部分。如果x在模式串里出现过则把模式串里最靠右的x对齐到主串的x位置上继续比。Boyer-Moore在模式串较长时性能非常优秀很多文本编辑器的查找功能就用它的变体。但它实现复杂度高两个规则都要维护跳转表面试时能讲清楚思路就已经是加分项。5.3 各匹配算法对比算法平均时间最坏时间额外空间特点朴素匹配O(n×m)O(n×m)O(1)实现简单短串好使KMPO(nm)O(nm)O(m)稳定线性适合重复查询Rabin-KarpO(nm)O(n×m)冲突多时O(1)哈希思想多模式友好Boyer-MooreO(n/m) 通常O(n×m)O(m)模式越长跳得越快做这道LeetCode题时我建议主学KMPRabin-Karp要能手写Boyer-Moore性质理解即可。这三种梯度正好对应面试考察的层级能不能写出来、能不能讲清楚、能不能做选型。6. 从题目到工作字符串匹配的真实战场6.1 编辑器与全文检索每次你在VSCode里按CtrlShiftF底层就是一个大规模的字符串匹配任务。项目里有几万个文件每个文件几千行要找某个函数名出现在哪里暴力匹配肯定不行。编辑器通常会对用户输入的搜索词进行算法选型搜索词短就走朴素匹配的优化版搜索词长就走类似Boyer-Moore的跳跃式匹配。这也是为什么有时候搜索词越长、搜索反而越快的反直觉现象。6.2 敏感词过滤与内容安全敏感词过滤系统是KMP思想最典型的工程应用。系统维护一个敏感词库用户提交的文本要在毫秒级内扫描完成。如果敏感词有成百上千个逐个匹配就行不通了。这时候用的是AC自动机——本质是在Trie树里跑KMP的失配跳转。你想一下KMP处理的是一个模式串在主串里的一次遍历AC自动机把它扩展成多个模式串同时匹配所有敏感词在主串上同时往前走一次遍历就全找出来这就是KMP思想的直接延伸。6.3 生物信息与数据清洗生物信息学里DNA序列由A、T、C、G四个碱基组成动辄上百万个字符。要在这么长的序列里找一段指定的基因片段而且允许一定程度的错误匹配朴素的遍历是远远不够的。很多比对工具的核心就是KMP、Boyer-Moore以及它们与动态规划的结合。再说数据清洗在日志系统里抽取特定格式的订单号、IP地址、错误码正则表达式是最常用的工具但如果你理解了匹配算法的原理你会知道为什么正则引擎在某些模式下会灾难性回溯——这也是为什么工程师要学算法不只是为了做题而是为了在线上出bug时能快速定位。做这道题最有价值的收获不是背下KMP的模板而是建立一种思维范式当你在一个序列里反复查找模式时哪些信息是计算过的、可以复用的这个思想从字符串匹配延伸到数组子序列匹配、树的遍历、动态规划的状态转移几乎贯穿整个算法学习路径。我自己每次面算法题都会引导候选人先聊暴力解再提示优化最后看他能不能自己推导出“复用已匹配信息”这个关键点——这道LeetCode 009恰好是最适合做这个思维训练的开端。