字符串匹配:KMP 算法
哪些公司问过
答案要点
- 朴素匹配失配时主串回退,最坏 O(n×m)
- KMP:主串指针不回退,利用 next 数组让模式串滑动,时间 O(n+m)
- next[i]:子串 p[0..i] 的最长相等真前后缀长度
- 失配且 j>0 时 j 跳到 next[j-1]、i 不动;j=0 时 i 前进;构造 next 也是双指针,O(m)
- Rabin-Karp:滚动哈希,平均 O(n+m);BM、Sunday 实践中也很快
易错点
- next 数组的下标含义和偏移搞错
- 失配时让主串指针回退
- 忘了处理模式串为空的情况
- 把哈希相同当作匹配成功,不做核对
面试官常见追问
- next 数组怎么构造?
- 为什么 KMP 的时间是线性的?
- Rabin-Karp 的原理是什么?
- KMP 适合什么场景?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场
- 实现 atoi:字符串转整数11 场