1. 从“子串”这个题说起它到底在考你什么某在线评测平台上有一道编号为4018的字符串基础题分类明确写着“字符串”。题干本身并不复杂给两个字符串模式串和文本串前者短一些、后者长一些要求判断模式串是否出现在文本串中并且输出它出现的所有起始位置或者总次数。我第一次看到这个题的时候觉得很眼熟和很多教材里的经典字符串匹配练习题几乎一模一样但真动手写了之后才发现越基础的题越能暴露问题。有人忘记考虑重叠匹配有人在模式串比文本串还长的时候直接越界还有人明明用对了算法却因为输出格式差一个空格反复提交。所以这篇文章想做的不只是给你一份能通过的代码而是把这个题目背后牵出的概念、算法、边界情况和调试思路全部掰开揉碎讲一遍。无论你刚开始接触字符串处理还是准备回顾匹配算法准备笔试这篇文章都适用。我会从暴力解法讲起再过渡到 KMP 和滚动哈希最后集中整理我会在这个题上反复踩的坑。整个过程尽量用平时交流的口吻写毕竟字符串题看起来简单真正拉开差距的地方恰恰是大家通常忽略的细节。这道题的核心是“在一个字符串里找另一个连续片段”也就是子串匹配。别小看这五个字它几乎是所有更复杂字符串算法的地基。文本编辑器里的查找功能、搜索引擎的关键词定位、日志系统里的敏感词筛选底层都会遇到同样的问题。把基础题吃透以后你会发现后面学 AC 自动机、后缀数组时顺畅很多因为它们本质上都在解决不同约束下的“怎么找得更快”。1.1 题面里的常见设定这类题目通常会在输入部分给出两行第一行是待查找的短串也就是模式串习惯记为 pattern第二行是长串也就是文本串习惯记为 text。输出则要求列出每一次匹配到的起始下标有的题从 0 开始数有的题从 1 开始数这一点必须提前看清楚不然很容易出现“样例过了一交全错”的情况。我第一次实现这个题时下意识以为找到第一个匹配位置输出即可但题目实际要的是所有出现的位置。比如 text 是ababapattern 是aba匹配会发生在下标 0 和下标 2一共两次。只看题面的人很容易漏掉第二个匹配尤其是当两次匹配区域有重叠时比如 text 是aaaaapattern 是aa你至少需要判断是按重叠方式计 4 次还是不重叠方式计 2 次。这类约定直接决定算法里成功匹配后下一步怎么走稍后我会专门展开。评测平台的输入规模通常不会在题面里明说但根据字符串分类下这个编号的常见风格长度很可能达到十万甚至百万级别。这个信息比题目本身更重要因为它直接表明暴力写法大概率会超时你必须提前想好更优的匹配策略。我的习惯是拿到字符串题先看两个东西字符串长度上限是多少以及是否涉及多组输入。长度决定复杂度上界多组输入则要求你在主循环里把初始化工作做好否则上一组数据留下的状态会污染下一组结果。1.2 子串不是子序列连续性的关键很多第一次接触字符串题的人会混淆两个概念子串和子序列。子串要求字符在原文中连续出现中间不能断开子序列则只要求字符按原顺序出现跳过的位置无所谓。举个例子text 是abcdef那么bcd是子串ace是子序列但不是子串因为a、c、e在原串里并不连续。这个区别对题目很重要。如果题目要求判断子序列那可以用贪心加双指针一边扫 text 一边匹配 pattern时间复杂度很低但如果题目要求子串双指针贪心就不成立了。你没法通过只记录“已经匹配到第几个字符”来判断一个连续子串是否出现因为你不知道当前匹配段的起点在哪。正因如此子串匹配才需要专门设计匹配算法而不是简单地扫描一遍就能解决。我在指导别人写题时喜欢让他们先手动模拟一遍拿一支笔在纸上画出 text 的每个字符再拿另一个小块当成 pattern 去滑动。你很快就会注意到暴力做法就是把 pattern 这个“小窗口”从左到右一格一格移动每到一个新位置就逐字符比较窗口里的内容是否一致。这个朴素的窗口思想贯穿后面所有优化方案KMP 也好、滚动哈希也好本质上都是在优化窗口移动和比较的速度。1.3 这道题背后真正考察的四个点这题虽然叫“字符串”但它考察的能力其实很综合。第一是问题拆解能力你要能把“找子串”抽象成“比较两个等长片段是否相等”的基本操作。第二是复杂度意识暴力解法正确无误但大规模数据下不可行你得判断什么场景该用什么算法。第三是边界处理能力空串、超长模式串、完全相等、只有一个字符等特殊情况都必须覆盖。第四是调试效率字符串题的错误样例往往不明显而且一旦错在匹配计数或下标转换上肉眼很难扫出来。这四个点对一个工程师来说比单纯记住某个算法更重要。很多人在刷题时背下了 KMP 模板但换个题目背景就不会用根本原因就是没理解模板里每一行代码到底在解决什么问题。所以这篇文章后面不会只给代码还会解释每一步的逻辑尤其是那些容易顺手写错的地方。理解了为什么这样做你才可能在真正需要的时候做出合适的变体。2. 暴力解法第一直觉能用但别急着交先写暴力版本不是浪费时间它是整个思考过程的起点。暴力解法很朴素把 pattern 和 text 的每一个可能起点对齐然后逐个字符比较。如果全部相等就记录当前位置。这个思路的好处是几乎不会写错非常适合用来确认自己对题意的理解是否正确。2.1 双循环逐位比较最直接的写法暴力版核心代码很短我第一版通常这样写#include iostream #include string #include vector using namespace std; vectorint bruteForceMatch(const string text, const string pattern) { vectorint positions; int n text.size(); int m pattern.size(); for (int i 0; i m n; i) { bool matched true; for (int j 0; j m; j) { if (text[i j] ! pattern[j]) { matched false; break; } } if (matched) { positions.push_back(i); } } return positions; }这里最需要注意的就是循环边界i m n。字符串的起点 i 从 0 开始如果 pattern 长度为 m那么最后一个可能的起点是 n - m所以i m n保证 i 不会越过这个位置。有些初学者习惯写成i n这样访问text[i m]时一定会越界轻则得到错误结果重则直接运行时错误。当 pattern 为空字符串时这段代码会直接跳过所有匹配。关于空串要怎么处理我放在后面的边界章节细说。现在先假设题目保证两个字符串都非空这样我们能集中精力理解匹配逻辑本身。2.2 三种典型数据规模下的耗时估算暴力算法最坏情况发生在 text 和 pattern 高度相似但始终差一点的时候。比如 text 全是apattern 也几乎全是a只在最后一个字符是b那么外层每移动一次内层几乎要比较完整个 pattern 才失败。比较次数就是文本长度乘以模式长度也就是 O(n * m)。我们拿实际数字感受一下当 n 和 m 都是 1000 时最坏比较次数是 100 万次现代计算机眨眼就能跑完当 n 和 m 都是 10 万时最坏比较次数是 100 亿次这就已经要跑几十秒甚至更久了如果两边都到 100 万最坏情况是 1 万亿次完全不现实。所以题目一旦把长度放到十万以上暴力解法基本可以判断为行不通。做得多了以后我拿到一个新字符串题会先在心里估算如果 n 和 m 都在 1000 以下暴力代码简单直接优化反而容易写错那就没必要用 KMP。如果 n 或 m 其中一个超过 10 万就应该直接考虑线性算法。复杂度分析不是纸上谈兵它决定了你会不会被第 10 组测试数据卡死。评测平台可不会因为你思路简单就手下留情它们往往专门准备了极端数据来淘汰暴力方案。2.3 暴力真正的价值当基准暴力解法虽然不能应对大规模数据但它的正确性非常容易验证。我在写完 KMP 或滚动哈希之后并不会直接把代码交上去而是会先用随机数据把暴力版和高效版的结果做对比两边输出完全一致再提交。这个方法我在后面专门讲调试时还会再提这里先记住一个结论暴力算法是验证其他算法是否正确的最好参照物。另一个容易被忽略的价值是暴力解法能帮你快速排查题意理解是否出错。比如你还没想清楚重叠匹配要怎么计暴力代码写出来以后跑一遍样例立刻就能看到自己默认的不重叠逻辑和题目要求是否一致。如果发现输出数量不对先别急着检查匹配逻辑极有可能是对“出现次数”的理解出了问题。3. KMP 算法用预处理把匹配时间降到线性KMP 的全称是 Knuth-Morris-Pratt三个人的名字放在一起。它出现在这个题目的高级解法里很合适因为只涉及单个模式串匹配而且数据规模一大线性时间几乎是必须的。KMP 的核心想法一句话就能概括已经匹配过的信息不要丢掉失配时利用这些信息跳到更有意义的位置继续比较而不是每次只往右挪一格从头再来。3.1 先理解“失配后该退回到哪里”用一个例子说明。text 是ababcabcabpattern 是abcab。暴力匹配从 text 下标 0 开始前三个字符aba中ab匹配但第三个字符a和c不匹配。按照暴力逻辑下一步要从 text 下标 1 重新开始。可是我们明明知道前两个字符是ab而 pattern 的开头也是ab这时候如果直接把 pattern 挪到下标 1必然还能匹配前面的一部分直接从头比较显然浪费了已知信息。KMP 的思路是提前计算 pattern 每个前缀的“最长相等前后缀长度”。当前缀和后缀存在一部分相同时失配后就可以把 pattern 向右滑动到能让这部分前缀重新对齐的位置。还是上面的例子pattern 的ab这个前缀同时也是已经匹配文本段的ab后缀所以失配后不需要把 pattern 移到 1只需要把 pattern 往右移到让这个公共部分重新重合的地方然后继续比较当前字符。这样做的效果是文本串的指针永远不回退整个扫描过程只需要遍历一次 text。这里有一个容易绕晕的地方KMP 并不直接计算“向右滑多少格”而是计算 next 数组表示“当匹配到 pattern 第 j 个字符失配时j 应该回退到多少”。回退之后前面的字符天然匹配继续往下比就可以了。很多模板喜欢用前缀函数 pi 数组表示同样含义实际上是一样的东西只是下标习惯不同。下面我会以 0 下标为基础讲解这是最容易和现代编程语言对齐的方式。3.2 next 数组是怎么算出来的next 数组的定义是对于 pattern 的前缀p[0..i]它能找到的最长相等真前缀和真后缀的长度。所谓真前缀、真后缀就是不能取整个字符串自己。比如 pattern 是aaaa那么p[0..1] aa的最长相等前后缀是a长度为 1p[0..2] aaa的最长相等前后缀是aa长度为 2。计算过程不需要对每个前缀重新判断而是利用之前已经算好的结果递推。核心代码这样写vectorint buildNext(const string pattern) { int m pattern.size(); vectorint pi(m, 0); for (int i 1; i m; i) { int j pi[i - 1]; while (j 0 pattern[i] ! pattern[j]) { j pi[j - 1]; } if (pattern[i] pattern[j]) { j; } pi[i] j; } return pi; }这段代码我第一次看的时候也觉得有点绕后来找到个比较顺的理解方式。变量 j 是当前已经匹配好的前后缀长度。我想给位置 i 计算 pi[i]本质上是想知道如果把当前位置的字符pattern[i]接到已有的前后缀后面还能不能继续保持相等。如果不相等就缩小 j尝试次长的一段前后缀直到相等或者 j 变成 0。这其实和后面匹配阶段失配时的处理逻辑完全一致所以理解了这段KMP 就理解了一大半。举个例子pattern 是ababac。计算到 i 等于 4 时pi[3] 等于 2也就是前缀abab的最长相等前后缀是ab。现在要处理 i 等于 4 的a先把 j 设为 2然后比较pattern[4]和pattern[2]两个都是a相等所以 j 加 1pi[4] 等于 3意味着ababa的最长相等前后缀是aba。整个过程不需要从零开始重新比较这就是递推的高效之处。3.3 匹配阶段完整代码匹配阶段同样维护一个指针 j表示当前已经匹配上了 pattern 的前 j 个字符。每次读入 text 的一个新字符如果和 pattern 第 j 个字符相等j 加 1如果不等就沿着 next 数组回退直到可以继续比或者回退到 0。当 j 等于模式长度 m 时说明找到了一个完整匹配记录起始下标为i - m 1然后继续用 next 数组回退避免漏掉重叠匹配。vectorint kmpMatch(const string text, const string pattern) { vectorint positions; int n text.size(); int m pattern.size(); if (m 0) { return positions; } vectorint pi buildNext(pattern); int j 0; for (int i 0; i n; i) { while (j 0 text[i] ! pattern[j]) { j pi[j - 1]; } if (text[i] pattern[j]) { j; } if (j m) { positions.push_back(i - m 1); j pi[m - 1]; } } return positions; }注意匹配阶段有两个j回退。第一个回退发生在字符失配时作用是回到一个仍然可能匹配的位置第二个回退发生在找到完整匹配后作用就是处理重叠匹配。如果你的题目要求不重叠的匹配次数那么第二个回退要改成j 0让匹配从当前位置之后重新开始。这个区别就是前面提到题意理解问题代码上只是一行之差结果却完全不同。3.4 三个容易忽略的写法坑第一个坑是下标 0 和 1 的混用。有些教材里 next 数组从下标 1 开始代码里的判断条件也会相应变化。我不建议看一个版本的代码又套着另一个版本的思路调试很容易把自己绕晕。选定一种统一从 0 开始的下标约定把 buildNext 和匹配阶段都建立在同一套约定上逻辑就清晰很多。第二个坑是空 pattern。buildNext 对空串会生成大小为 0 的数组匹配阶段访问pattern[j]时 j 也是 0理论上不会越界但pi[m - 1]中 m 减 1 等于 -1访问就会越界。所以我在匹配代码里一开始就特判了空 pattern。如果题目保证 pattern 非空这个特判可以省略但加上它不会影响正确性反而能防止因数据约定变化而翻车。第三个坑是 int 和 unsigned 的混用。text.size()返回的是无符号整数如果直接用text.size() - pattern.size()作为循环条件当 pattern 比 text 长时这个值的二进制解释会变成一个非常大的正数循环直接失控。我在写边界处理时通常会先把长度转成 int再参与计算避免这类隐蔽问题。4. 滚动哈希和内置函数实战中的另一种思路KMP 的优点是稳定、无碰撞但并不是唯一选择。字符串匹配还有一个非常实用的家方向把字符串映射成整数通过比较哈希值来判断两个子串是否相等。这就是 Rabin-Karp 滚动哈希思想。它的匹配过程中不需要像 KMP 那样跳来跳去只需要计算一次模式串哈希再顺着文本串滑动计算每个窗口的哈希值时间上也是 O(n m)。4.1 Rabin-Karp 的原理与代码框架原理其实可以理解成把一个字符串看成某种进制的大整数。比如字符只包含小写字母我就把a到z分别看成数字 0 到 25然后选定一个大于字符集大小的进制 BASE一般取 31 或 131 都可以。字符串abc的哈希值就相当于0 * BASE^2 1 * BASE 2当然实际计算时会取模防止数字太大。滑动窗口时不需要每次重新计算整个窗口的哈希。假设当前窗口是text[i..im-1]下一个窗口只是把最左边字符去掉、右边新增一个字符。所以新的哈希值可以通过旧哈希值用加减乘运算得到这就是“滚动”的含义。为了去除最左边的字符还需要提前算出BASE^(m-1)对模数取余后的值。vectorint hashMatch(const string text, const string pattern) { vectorint positions; int n text.size(), m pattern.size(); if (m 0 || m n) return positions; const long long BASE 31LL; const long long MOD 1000000007LL; long long hashPattern 0, hashWindow 0, power 1; for (int i 0; i m; i) { hashPattern (hashPattern * BASE pattern[i]) % MOD; hashWindow (hashWindow * BASE text[i]) % MOD; if (i m - 1) { power (power * BASE) % MOD; } } for (int i 0; i n - m; i) { if (hashWindow hashPattern) { bool same true; for (int j 0; j m; j) { if (text[i j] ! pattern[j]) { same false; break; } } if (same) { positions.push_back(i); } } if (i n - m) { hashWindow (hashWindow - text[i] * power) % MOD; if (hashWindow 0) hashWindow MOD; hashWindow (hashWindow * BASE text[i m]) % MOD; } } return positions; }代码里的same循环是为了处理哈希碰撞。理论上不同字符串可能算出相同哈希值极少数情况下会产生误判所以哈希相等后要再做一次真正的字符串比较来确认。这样处理后Rabin-Karp 在最坏情况下可能退化到和暴力一样的复杂度但在正常数据上的表现非常接近线性而且代码写起来比 KMP 直观得多。使用哈希时选 BASE 和 MOD 有讲究。BASE 要保证和字符范围互质不要比字符集小否则不同字符会映射到同一个数。MOD 最好选一个大质数比如 1e97这样不同字符串发生碰撞的概率很低。还有一点如果担心哈希碰撞可以用两个不同模数分别计算只有两个哈希都相等才确认匹配这一招在很多题目里也能用缺点是计算量翻倍。4.2 标准库 find 也很好用但要注意场景如果只是想知道 pattern 是否在 text 中出现C 标准库里的string::find是最省事的方案string text, pattern; cin text pattern; if (text.find(pattern) ! string::npos) { cout found endl; } else { cout not found endl; }标准库实现通常会结合多种优化策略实际速度非常快。而且它返回的是第一个匹配位置对绝大多数工程场景够用了。但放到这个题里就有点尴尬因为题目往往要求输出所有位置你需要循环查找每找到一次还要从下一个位置开始继续找写法变得繁琐而且每次查找内部都重新做准备工作整体效率反而未必比 KMP 高。我认为这类基础题不太适合直接用find提交。不是因为不能用而是因为刷题的目的是理解匹配过程本身。KMP 和 Rabin-Karp 的代码量都不大亲手实现一遍以后你对字符串匹配的敏感度会提升一个档次。而find是一个黑盒用多了会让自己停留在“调包”层面。实际工作时我经常用find毕竟效率和正确性都有保证但作为学习我更推荐先写一遍底层算法。4.3 各方案横向对比我把这三种常见方案的适用场景整理成一个表方便在做题前快速决策方案时间复杂度空间复杂度优点需要注意的问题暴力匹配O(n*m)O(1)代码简单正确性直观数据量大时会超时KMPO(nm)O(m)时间稳定无碰撞next 数组逻辑需要一定理解成本Rabin-Karp 哈希平均 O(nm)O(1)思路简单适合滚动窗口场景有碰撞可能需要二次确认标准库 find通常接近线性O(1)调用简单工程可靠多次查找时效率不高在实际做题时如果模式串只有一个长度达到十万级别我会优先用 KMP。如果模式串有多个需要同时在一长串文本里查找那么 KMP 不太好直接扩展可以考虑 AC 自动机或者把 Rabin-Karp 改进成多模式版本。如果题目里字符串长度很小直接暴力即可没必要为了炫技引入更复杂的代码因为任何一点实现错误都会增加排查成本。5. 边界与细节WA 和 RE 都藏在哪里字符串题目最容易出现的问题不是算法不会而是边界条件没有处理好。我见过太多人把 KMP 模板背得滚瓜烂熟结果提交后答案错误最后发现是空字符串、重叠计数或者下标转换出了问题。这一节把常见的坑集中梳理一遍并给出排查思路。5.1 空串和长度倒挂题目如果没有明确说字符串非空那就要考虑 pattern 为空的情况。理论上有两种处理方式一种认为空串是任意字符串的子串出现位置从 0 到 n 每个位置都算一次另一种认为题目不涉及空串直接特判输出空结果即可。实际比赛中我倾向于先看题面有没有给字符串长度范围如果明确长度大于等于 1就完全不用关心空串。如果没给稳妥做法是提前返回空结果而不是让代码崩溃。长度倒挂是另一种更常见的风险。pattern 比 text 还长时它不可能成为 text 的子串直接输出 0 或者不输出任何位置就行。但很多初版代码会在循环条件里写出未定义行为尤其是用text.size() - pattern.size()这种写法前文已经提到无符号整数相减可能会得到一个巨大正数导致循环完全失控。我在写代码时习惯先把长度转为 int 并用i m n做比较就能从根上避开这个问题。5.2 重叠匹配与重复计数这是最容易导致答案错误的地方。什么是重叠匹配举个例子text 为bananapattern 为ana从 0 开始数第一次出现在下标 1第二次出现在下标 3。细看会发现第一次匹配的后两个字符和第二次匹配的前两个字符是重合的但它们是两次独立出现因为它们对应不同的起始位置。如果题目统计的是“出现次数”一般默认就是按起始位置计数允许重叠。KMP 代码里找到完整匹配后j pi[m - 1]正是为了让下一次匹配从重叠部分开始继续。如果你把它改成j 0得到的次数就是不重叠次数。比如 text 为aaaapattern 为aa允许重叠时答案是 3 次不允许重叠时答案是 2 次。这个差异要是不提前确认写出来的代码在部分数据上必然出错。5.3 读入、输出和评测机的约定很多评测题目会提供多组测试数据读入会持续到文件末尾所以主循环要写成string text, pattern; while (cin pattern text) { vectorint ans kmpMatch(text, pattern); for (int i 0; i (int)ans.size(); i) { if (i) cout ; cout ans[i]; } cout endl; }注意这里我把 pattern 放前面读因为在原始题面里模式串通常先输入。实际以你看到的题面为准但处理多组输入时一定要记得每组之间把累积状态清空。如果使用了子串输出还要留意输出格式是每行一个位置还是一行拼接输出。像我是按“空格分隔同一行”这种方式写的空结果时会单独输出一个空行这通常能被评测机接受但如果题目明确要求什么也不输出就需要做额外判断。5.4 报错信息排查速查表把常见的报错类型和原因整理成速查表遇到问题时可以快速对照评测状态最可能的原因排查方向答案错误重叠匹配逻辑不对检查完整匹配后回退用的是 pi[m-1] 还是 0答案错误下标起始位置算错确认输出是从 0 开始还是从 1 开始运行时错误数组越界重点检查 unsigned 减法和空串特判超时暴力算法或哈希退化换 KMP 或改进哈希二次确认逻辑格式错误多余空格或换行对比题目输出样例调整输出拼接方式字符串题的诊断往往比普通题更依赖测试样例因为错误输出可能只出现在极端边界。所以不要只盯着题目给的样例要自己构造一些极端数据去验证。下面这一节我会分享我日常用的测试方法这套方法不仅适用于本题目对其他算法题也很有帮助。6. 值得长期坚持的调试方法和扩展方向到这里算法本身已经讲完了。但我想聊一个平时很多人忽略的问题怎么保证自己写的字符串代码在各类数据上都是对的。只看题目样例远远不够必须主动做测试。我几乎每写完一个字符串匹配算法就会立刻进入对拍模式。6.1 用随机数据对拍对拍就是同时跑一个可信的基准程序和当前写的程序在大量随机数据上比较结果。对于这道题基准程序就是暴力匹配。我会写一个简单的数据生成脚本随机生成 text 和 pattern长度可以从小到大逐渐增大然后把暴力结果和 KMP 结果都输出到文件再用脚本对比。只要两组结果在所有随机数据上都一致我才会放心去提交。除了随机数据还要加入一些针对性的构造数据。比如 text 全为同一个字符pattern 也全为同一个字符pattern 的前缀和后缀高度相似匹配恰好发生在 text 的最开头和最末尾pattern 长度比 text 长 1pattern 与 text 完全相等。这些特殊输入最容易暴露边界问题。6.2 关注数据范围再选算法我现在拿到字符串题的第一反应不是立刻写代码而是先根据数据范围判断复杂度。如果 n 和 m 都在 1000 以内暴力就很合理如果达到一万暴力勉强可以但最好做好优化如果超过十万基本只考虑线性算法。这个方法看似简单却能避免很多无意义的超时。顺便说一句KMP 的空间复杂度是 O(m)当模式串长度为百万时内存占用也只有几 MB完全不需要担心。滚动哈希则几乎不占额外空间适合内存受限的场景。我在模拟项目里测过一个长度五百万的文本串暴力匹配跑了大概三分钟KMP 几乎是秒出结果。差距这么明显原因就在于暴力在遇到“最后一个字符才失配”这种数据时成本太高而 KMP 的每个字符平均只会比较常数次。字符串题考复杂度意识不是没道理的一个设计良好的算法能让规模五百万的数据在零点几秒内跑完。6.3 从子串匹配扩展出去这道题解决的是单模式串匹配问题但它的思想可以延伸到很多方向。如果你要在同一个文本串里同时找多个模式串每个模式串都跑一次 KMP代价就是 m 个模式串造成的重复扫描文本。这时候应该考虑 AC 自动机它把多个模式串合并成一棵 Trie 树并借用了 KMP 的失配指针思想一次扫描就能匹配出所有模式串。如果你只关心模式串在文本里的整体频率还可以用 Z 函数代码更短专门解决“子串出现次数”这一类问题。如果文本串本身不变化但会有大量不同的模式串进来查询那么预处理后缀数组加二分会是很强的方案。每次查询可以通过后缀排序后的数组快速定位目标子串的范围在需要频繁查询的工程场景里非常实用。这里我不深入展开但希望你看完本文后能建立起一个印象基础匹配只是起点后面的路还很长。最后再分享一个我个人的小习惯写完这种字符串题我一定会把完整匹配次数、第一个匹配位置、最后一个匹配位置一次性验证一遍。因为这三个值分别对应了匹配流程、起始下标计算和重叠回退逻辑能同时通过这三关代码大概率就稳了。这道“子串”题正是我用这个方法反复验证过的基础题每次重新实现我都会再收获一点对字符串匹配的体会建议你也试试。