实现 strStr:第一个匹配项的下标(LC28)
哪些公司问过
答案要点
- needle 为空返回 0,needle 更长直接返回 -1
- 暴力枚举起点 0 到 n-m 逐字符比较,最坏 O(nm)
- KMP 预处理 next 数组:前缀的最长相等真前后缀长度
- KMP 失配时主串指针不回退,时间 O(n+m)、空间 O(m)
- Rabin-Karp 滚动哈希期望 O(n+m),哈希命中需逐字符校验
易错点
- 枚举起点上界写成 n 而不是 n-m,导致越界
- 忘记处理 needle 为空的情况
- KMP 求 next 时回退写成 j=next[j],导致死循环或错误
面试官常见追问
- KMP 的 next 数组怎么求?
- 为什么暴力法最坏是 O(nm)?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场