面试题库 › Java 后端 › 字符串匹配:KMP 算法

字符串匹配:KMP 算法

难度 ★★★在 18 场真实面经中被问到 方向:Java 后端考点:数组与字符串

哪些公司问过

腾讯5美团2阿里巴巴2海康威视2蔚来1华为1小红书13601深信服1人人网1

常见岗位:Java 后端、Go 后端、安卓、嵌入式软件、C/C++ 软件开发

答案要点

  1. 朴素匹配失配时主串回退,最坏 O(n×m)
  2. KMP:主串指针不回退,利用 next 数组让模式串滑动,时间 O(n+m)
  3. next[i]:子串 p[0..i] 的最长相等真前后缀长度
  4. 失配且 j>0 时 j 跳到 next[j-1]、i 不动;j=0 时 i 前进;构造 next 也是双指针,O(m)
  5. Rabin-Karp:滚动哈希,平均 O(n+m);BM、Sunday 实践中也很快

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题