KMP算法失败函数f的计算
失败函数 f 的计算挺有意思，属于 KMP 算法里一个关键的小步骤。它的作用啊，说白了就是在模式串里提前知道“下次从哪开始比”，省得你白白回溯。f(0)设为–1 是惯例，后面每一个f(j)，其实就是找前缀后缀最长的公共部分，字符一样就进一位，不一样就往前跳，跳回之前算好的 f 值，直到跳不动。这样匹配的时候，就能又快又省事。
KMP这块如果你还不熟，推荐你看看这篇：
- KMP 字符串匹配算法，讲得比较清楚，例子也够多
- kmp 模式匹配算法，这个更偏 C++实现，写法上更贴工程
另外，如果你对字符串匹配感兴趣，其他几个方向也蛮值得一看：
- DidYouMean2：用Levenshtein 距离做模糊匹配，比较适合输入纠错那类
- Rabin-Karp 算法：用模运算+哈希来加速匹配，思路不一样
- PHP 字符串函数参考：如果你写后端，字符串频繁，翻一翻挺有用
如果你是做搜索、编辑器、IDE 插件那种需求，KMP加上这些高级匹配算法一起用，效率和体验都能上一个台阶。嗯，算法理解透了，业务起来也更顺手。
文件大小：4.19MB
评论区