模拟实现strstr：从朴素匹配到KMP

模拟实现strstr从朴素匹配到 KMP1. 从最自然的实现开始strstr的任务很直接在haystack中寻找needle第一次完整出现的位置。如果找到返回该位置如果找不到返回NULL。如果暂时完全不考虑更复杂的算法最自然的做法就是不断假设一个候选起点。假设haystack[i]可能对应needle[0]那么就从这里开始逐字符向后比较haystack[i] needle[0] haystack[i 1] needle[1] haystack[i 2] needle[2] ...如果needle全部匹配成功当前候选起点就是答案。如果中途失败则说明haystack[i]不可能是目标子串的起点于是令候选起点向后移动一位再重新开始。这就是朴素匹配。它的实现简单而且非常符合strstr本身的语义。但是它存在一个明显的问题一次匹配可能已经成功比较了很多字符最后才失败而失败以后这些已经得到的信息全部被丢掉。例如haystack: a b a b a b a c needle: a b a b a c ✓ ✓ ✓ ✓ ✓ ×前五个字符已经确定相等最后一个位置才发生失配。朴素算法此时会重新寻找新的起点并从needle[0]开始重新比较。于是自然会产生一个问题前面已经成功比较过那么多字符这些信息真的必须全部丢掉吗KMP 就是从这个问题开始的。2. 匹配失败以后哪些信息仍然有价值上面的失败发生以前我们已经确定haystack 中刚刚成功匹配的部分 needle 的某段前缀例如已经成功匹配ababa那么haystack中对应区域的内容也一定是ababa现在观察这段字符串ababa它存在前缀aba 后缀aba也就是说刚才成功匹配区域末尾的aba恰好又等于needle开头的aba因此下一轮匹配时这三个字符其实没有必要重新比较。可以直接认为haystack: a b a b a b a c needle: a b a b a c ✓ ✓ ✓前三个字符已经匹配成功。于是KMP 真正想利用的并不是一般意义上的“重复块”而是已经匹配成功的部分中是否存在一个后缀同时也是needle的前缀。而且这样的部分越长越好因为能够继承的匹配状态也越多。3. 为什么最后只需要研究needle一开始问题似乎是haystack 已匹配区域的某个后缀 needle 的某个前缀但实际上不需要重新研究haystack。因为刚才已经证明haystack 已匹配区域 needle 已匹配的前缀所以haystack这一块内部具有什么结构完全可以通过needle自身得到。于是问题被转化成对于needle的某一段前缀它自身最长的“相同前缀和后缀”有多长这样就可以提前对needle进行一次预处理把这些信息保存下来。4. LPS 表的定义设needle的长度为len其有效字符下标为0 ... len - 1建立数组lps[len]规定lps[i]表示在needle[0..i]中最长的“真前缀 后缀”的长度。例如needle a b a b a 0 1 2 3 4对于needle[0..4] ababa存在前缀aba 后缀aba而且aba已经是最长的相等前后缀因此lps[4] 3如果lps[i] k那么严格意味着needle[0 .. k-1] needle[i-k1 .. i]这里必须强调两件事。第一前缀必须从needle[0]开始。第二后缀必须严格结束在needle[i]。不能把字符串内部任意一段相同子串都算进来否则这些信息无法用于后续状态继承。同时还必须要求是真前缀。如果允许整个needle[0..i]自己和自己比较那么任何位置都会得到lps[i] i 1这样的信息没有任何意义。5. 初始状态对于needle[0]整个区间只有一个字符。它不存在非空的真前缀也不存在能够与之对应的非空真后缀因此lps[0]0;这就是 LPS 构造的初始状态。从lps[1]开始后面的状态都可以利用之前已经计算出的状态继续推导。这一点很有动态规划的味道后面的状态并不是重新从零计算而是在利用已有结果。6. 从lps[i-1]推导lps[i]现在准备计算lps[i]假设mlps[i-1];那么根据定义已经知道needle[0 .. m-1] needle[i-m .. i-1]可以把它理解成needle[0..i-1] [ 0 ...... m-1 ] ........ [ i-m ...... i-1 ] 前缀 m 后缀 m现在新加入needle[i]最理想的状态当然是原来的前后缀可以同时向后扩展一位。左边前缀接下来需要加入的是needle[m]右边后缀新加入的正是needle[i]所以首先只需要检查needle[m]needle[i]如果成立那么原来长度为m的前后缀成功延长lps[i]m1;真正困难的是两者不相同时怎么办。7. 第一个错误想法直接归零如果needle[m] ! needle[i]最容易产生的想法就是lps[i]0;但这并不成立。当前失配只能说明长度为m的这个最长前后缀无法继续延长。却不能说明所有更短的前后缀也都无法延长。完全可能存在一个更短的前后缀它的下一个字符恰好等于needle[i]所以不能直接归零。8. 第二个错误方向不要求后缀结束在当前末尾另一个自然想法是既然[i]破坏了原来的状态是否可以忽略它继续保留[0..i-1]中已有的前后缀这样同样不行。因为我们现在要求的是lps[i]它描述的是整个needle[0..i]的后缀。后缀按照定义必须结束在i如果允许结束在前面的任意位置那就已经不再是整个[0..i]的后缀而只是内部某段子串。更重要的是这种信息无法用于后面的 KMP 搜索。KMP 能够继承旧状态的原因正是因为后缀紧贴在当前已经匹配区域的末端新的字符可以直接接在它后面。因此“后缀必须结束在当前末尾”这个条件不能放松。于是问题变成怎样寻找一个更短但仍然严格结束在i-1的合法前后缀9. 为什么可以查lps[m-1]重新回到已经知道的事实needle[0 .. m-1] needle[i-m .. i-1]这两个长度为m的区域完全对应相等。现在设nlps[m-1];那么根据定义needle[0 .. n-1] needle[m-n .. m-1]也就是说在左边长度为m的前缀内部又存在一个更短的长度为n的相等前后缀。而我们已经知道整个长度为m的左右两块完全相等因此左边大块最后n个字符needle[m-n .. m-1]也一定等于右边大块最后n个字符needle[i-n .. i-1]于是得到needle[0 .. n-1] needle[i-n .. i-1]这说明n依旧是needle[0..i-1]的一个合法前后缀长度而且它的后缀仍然紧贴着i-1。所以接下来可以继续尝试needle[n]needle[i]如果相等lps[i]n1;如果仍然不相等则继续nlps[n-1];于是形成一条严格缩短的候选链m ↓ lps[m - 1] ↓ lps[lps[m - 1] - 1] ↓ ... ↓ 0这不是随便找一个更小的长度而是在从长到短寻找所有仍然严格结束在i-1的合法前后缀。10. 从数学递推关系到程序控制逻辑理解m → lps[m - 1]是一回事。真正把它写成程序又是另一回事。算法实现并不是把数学公式翻译成几条赋值语句就结束了还需要确定哪些变量表示什么状态哪些状态需要循环循环什么时候继续什么时候退出退出以后还剩哪些情况没有处理。对于lps[i]程序中最重要的状态变量就是m它始终表示当前正在尝试的前后缀长度。初始化size_tmlps[i-1];表示首先尝试上一状态能够提供的最长候选。现在的问题可以被程序化地重新描述成当前长度为 m 的候选 ↓ needle[m] 能不能和 needle[i] 接上如果能m → m 1当前状态计算结束。如果不能则m → lps[m - 1]换一个更短但仍然合法的候选再继续尝试。因为一次回退之后仍然可能失败所以这里不能只使用一次if而需要不断重复尝试 ↓ 失败 ↓ 回退 ↓ 再尝试这自然对应while于是得到while(m0needle[m]!needle[i]){mlps[m-1];}这里两个循环条件分别有明确含义。m0表示仍然存在一个非空的旧前后缀状态可以继续回退。而needle[m]!needle[i]表示当前候选仍然无法被新字符[i]延长。所以整个while的含义就是当前候选无法延长而且仍然存在更短的合法候选时就继续回退。11. 为什么退出while以后还需要一次判断经过while(m0needle[m]!needle[i]){mlps[m-1];}以后循环可能因为两种不同原因结束。第一种情况是needle[m] needle[i]说明已经找到了可以延长的候选。此时m;即可。第二种情况是m 0这里不能立即写lps[i]0;因为m 0只表示所有旧的非空前后缀候选都已经失败。但此时仍然存在一种新的可能needle[0] needle[i]如果成立那么虽然旧状态全部失败却可以重新形成长度为1的前后缀。由于现在m0所以needle[m]needle[i]实际上正好就是needle[0]needle[i]因此退出循环以后统一进行if(needle[m]needle[i]){m;}即可同时处理找到某个更短的旧候选以及全部旧候选失败但产生长度 1 的新状态最后lps[i]m;于是整个 LPS 构造被压缩成size_tmlps[i-1];while(m0needle[m]!needle[i]){mlps[m-1];}if(needle[m]needle[i]){m;}lps[i]m;这几行代码虽然很短但每一行都来自前面的状态分析并不是需要直接记忆的公式。12. LPS 构造的完整控制过程把它放回外层循环以后lps[0]0;for(size_ti1;ilen2;i){size_tmlps[i-1];while(m0needle[m]!needle[i]){mlps[m-1];}if(needle[m]needle[i]){m;}lps[i]m;}这里i负责逐步扩大当前研究的needle前缀needle[0..1] needle[0..2] needle[0..3] ...而m负责在当前前缀内部维护当前正在尝试的最长合法前后缀长度。所以这两个变量承担的职责完全不同。13. 有了 LPS 以后搜索阶段需要维护什么状态真正搜索haystack时使用size_ti0;size_tj0;其中i表示当前准备处理的haystack字符位置。而j具有两个完全一致的含义已经成功匹配的 needle 字符数量以及下一次准备比较的 needle 下标例如j 3意味着needle[0] needle[1] needle[2]已经匹配成功下一次应该比较needle[3]正因为“已匹配长度”和“下一下标”在从 0 开始编号时数值相同所以代码才可以直接使用一个j表示这两个状态。14. 字符匹配成功时如何更新状态如果haystack[i]needle[j]说明当前这一对字符也匹配成功。因此i;j;现在i指向haystack中下一个尚未处理的字符。而j表示已经成功匹配的needle字符数量。但这里不能简单结束当前分支。因为j;以后可能刚好出现jlen2;这意味着needle的最后一个字符刚刚也匹配完成。也就是说完整匹配状态正是在这里产生的。因此必须立刻检查if(jlen2){...}15. 为什么完整匹配判断必须放在成功分支内部这一点看起来只是代码位置问题实际上非常容易写错。假设haystack xxabc needle abc最后一次比较haystack[4] needle[2]成功。随后i;j;得到i 5 j 3 len2 3所以j len2完整匹配已经发生。同时haystack[5] \0如果不在这里立即检查而是打算等下一轮循环再判断下一轮首先遇到while(haystack[i]!\0)条件失败。循环直接结束。最后returnNULL;于是会出现明明刚刚已经完整匹配却因为匹配终点恰好也是haystack的终点成功状态没有得到处理。所以成功状态必须在产生以后立即捕获。16. 为什么不能把j len2随便塞进失配分支链还存在另一个问题。假设把代码写成类似if(haystack[i]needle[j]){i;j;}elseif(j0){jlps[j-1];}elseif(jlen2){...}这同样错误。因为j len2一定同时满足j 0也就是说“完整匹配成功”状态和“存在部分历史匹配”状态发生条件重叠。如果控制顺序不正确已经完整匹配成功的状态反而可能被jlps[j-1];回退掉。更根本的问题在于j len2本来就不是一种“失配状态”。它是一次字符匹配成功以后产生的完成状态。所以控制结构本身应该具有层级本次字符比较 │ ├─ 成功 │ │ │ ├─ i │ ├─ j │ │ │ └─ j len2 ? │ ├─ 是完整匹配立即返回 │ └─ 否继续 │ └─ 失败 │ ├─ j 0 │ └─ 回退 j │ └─ j 0 └─ 前进 i这样控制流才与算法状态完全一致。17. 完整匹配以后怎样得到起点当jlen2成立时j表示已经完整匹配的字符数量。同时i已经因为最后一次成功匹配而前进到了匹配区域之后。例如haystack: x x a b c 0 1 2 3 4 needle: a b c完整匹配以后i 5 j 3所以匹配起点就是5 - 3 2即haystack(i-j)因此完整处理为if(jlen2){free(lps);return(char*)haystack(i-j);}这个位置既能及时捕获成功状态也可以直接利用当前i、j算出目标起点。18. 失配以后为什么只回退j如果haystack[i]!needle[j]但j0说明前面needle[0 .. j-1]已经成功匹配。因此查lps[j-1]就可以知道这j个已匹配字符中还有多长的前缀状态能够继续继承。所以jlps[j-1];这里有一个极其重要的实现细节i不能移动。因为当前haystack[i]只证明haystack[i] ! 旧 needle[j]但没有证明haystack[i] ! 回退后的新 needle[j]当前字符仍然可能成为新状态下的下一个匹配字符。因此失配但j 0时只能改变j不能i;19. 什么时候才能移动i只有当j 0同时haystack[i]!needle[0]时才说明当前haystack[i]连needle的第一个字符都无法匹配因此它不可能再属于任何以当前状态为基础的候选匹配。这时才可以i;所以搜索主体最终形成三个状态if(haystack[i]needle[j]){i;j;if(jlen2){free(lps);return(char*)haystack(i-j);}}elseif(j0){jlps[j-1];}else{i;}现在这段代码可以直接按状态解释匹配成功 → 双方前进 → 检查是否完成 匹配失败但有历史状态 → 只回退 needle 匹配失败且已经无状态可退 → 丢弃当前 haystack 字符20. KMP 真正避免了什么KMP 并不是让haystack一次跳过很多字符。事实上i基本仍然是逐字符向前移动。真正重要的是i永远不会回退。朴素算法在一次深度匹配失败以后会把候选起点向后移动再重新读取之前已经比较过的haystack字符。KMP 则保留haystack 当前扫描位置只通过jlps[j-1];改变needle 当前匹配状态所以之前已经确认过的信息不会被全部丢掉。21. 为什么不断回退仍然是线性复杂度设haystack长度为nneedle长度为m。搜索阶段中j虽然可能反复回退但每一次j;一定伴随i;因此j的累计增长量受到i的累计增长量限制。而i最多前进n次。另一方面jlps[j-1];每次都会让j严格减小。所以所有回退都只是在消耗此前已经积累出来的匹配长度。因此搜索阶段总复杂度为O(n) O(n)O(n)LPS 的构造过程同样使用这种“增长 严格回退”的结构所以复杂度为O(m) O(m)O(m)最终O(nm) O(nm)O(nm)这里使用的是摊还分析的思想并不是要求每一次循环都只执行固定数量的操作。22. 理论复杂度更好不代表实际一定更快KMP 的最坏复杂度为O(nm) O(nm)O(nm)而朴素算法最坏可能达到O(nm) O(nm)O(nm)但这并不意味着实际使用中 KMP 一定更快。普通字符串中大量候选位置往往在第一个或前几个字符就会失败。例如haystack 普通文本 needle xyz...很多候选位置实际上只需要比较一次haystack[i] ! x就结束。此时朴素算法虽然最坏复杂度仍然是O(nm)实际工作量却可能接近一次线性扫描而且没有 LPS 没有额外预处理 没有状态回退 控制逻辑更加简单因此常数开销可能更低。而高度重复的数据haystack aaaaaaaaaaaaaaaaa... needle aaaaaaaab则可能让每个候选位置都进行大量比较以后才失败。这时 KMP 的优势会迅速扩大。23. 曾尝试使用经验系数自动选择算法曾经尝试使用(n−m1)mnm \frac{(n-m1)m}{nm}nm(n−m1)m​估计朴素算法与 KMP 的工作量关系并希望找到一个经验系数Kscore K → naive score K → KMP但实际 benchmark 表明这种模型无法可靠工作。例如n 256 m 64 score 38.60普通数据fast-miss: naive ≈ 196 ns KMP ≈ 448 ns朴素算法更快。而高度重复数据repeat-miss: naive ≈ 5485 ns KMP ≈ 937 nsKMP 又明显更快。也就是说n 相同 m 相同 score 相同最优算法仍然可能完全相反。真正影响朴素算法工作量的是每个候选位置实际能够向后匹配多深才失败。更接近其真实工作量的描述应该是∑Ls \sum L_s∑Ls​其中L_s表示候选起点s实际进行了多少次字符比较。而仅仅知道n和m无法得到这些信息。因此最终放弃使用单一经验系数进行所谓的自动智能分流。24. 最终实现策略最终选择默认使用朴素算法需要时显式启用 KMP。这并不是认为朴素算法在理论上优于 KMP而是因为对于当前strstr模拟实现朴素算法直接表达函数语义普通数据下常数开销较低KMP 主要提供更好的最坏情况保证单纯根据字符串长度无法可靠预测两者实际性能。因此 KMP 作为一个可选实现保留。25. 公共接口与内部实现职责对外只希望暴露myStrstr(...)而naiveStrstr(...)kmpStrstr(...)只是实现细节。因此二者不进入公开头文件并可以在实现文件中声明为static公共入口统一完成strlen以及if(len20)return(char*)haystack;if(len2len1)returnNULL;这些属于strstr本身的公共语义不属于某一种具体搜索算法。这样不需要在 naive 和 KMP 内部分别复制同样的边界处理。26. 为什么main.c中的宏不能直接影响另一个.c文件希望使用#defineUSE_KMP_STRSTR直接在调用方选择 KMP。但是如果myStrstr的实现位于另一个.c文件中那么#defineUSE_KMP_STRSTR只影响当前翻译单元。例如main.c strstr.c在main.c中定义的宏不会自动传播给strstr.c所以不能简单在strstr.c中写#ifdefUSE_KMP_STRSTR并期待main.c中的宏能够控制它。27. 通过宏包装公开调用为了仍然允许调用者写#defineUSE_KMP_STRSTR#include...来控制算法可以让宏控制“调用方式”而不是控制另一个翻译单元的编译过程。例如头文件#ifdefUSE_KMP_STRSTR#definemyStrstr(haystack,needle)\myStrstrImpl((haystack),(needle),true)#else#definemyStrstr(haystack,needle)\myStrstrImpl((haystack),(needle),false)#endif真实入口char*myStrstrImpl(constchar*haystack,constchar*needle,bool useKmp);内部统一处理边界条件以后if(useKmp){returnkmpStrstr(haystack,len1,needle,len2);}returnnaiveStrstr(haystack,len1,needle,len2);这样#defineUSE_KMP_STRSTR#include...时myStrstr(...)自动走 KMP。没有定义宏时则默认走朴素实现。宏必须位于相关头文件之前因为选择过程发生在预处理阶段。28. 最终理解这次实现strstr真正值得保留下来的并不是某张next表也不是mlps[m-1];这种看起来精巧的代码本身。更重要的是完整的推导过程朴素算法深度匹配失败 ↓ 发现已经取得的信息被全部浪费 ↓ 寻找能够继续继承的匹配状态 ↓ 得到“已匹配后缀 needle 前缀” ↓ 利用已匹配内容本身等于 needle 前缀 ↓ 把问题完全转化成研究 needle 自身 ↓ 定义 LPS ↓ 最长状态延长失败时发现不能直接归零 ↓ 要求更短候选仍然紧贴当前末尾 ↓ 利用已知相等的大前后缀 ↓ 自然推出 lps[m - 1] 回退链 ↓ 再把数学状态转化成 m 的 while 控制过程 ↓ 搜索阶段用 j 表示“已匹配长度 / 下一 needle 下标” ↓ 失配时只回退 j不回退 i ↓ 成功后立即检查 j len2 ↓ 在完成状态产生的瞬间捕获结果所以 KMP 的难点实际上有两层。第一层是怎样把“匹配失败以后哪些信息仍然有效”抽象成前后缀数学模型。第二层是怎样把这个数学模型准确地转换成变量状态、循环条件和分支控制而不在边界状态上丢失信息。后者尤其容易被最终只有几行的代码掩盖。KMP 的核心思想最终可以概括为一次失败只否定当前候选状态并不意味着此前已经获得的全部信息都失效。而实现层面的核心则是每一种状态都必须在它产生的正确时刻被处理不能只知道数学关系却忽略控制流中的状态生命周期。