面试题库 › 客户端 › 长文本中如何匹配大量关键词

长文本中如何匹配大量关键词

难度 ★★☆在 1 场真实面经中被问到 方向:客户端考点:数组与字符串

哪些公司问过

字节跳动1

常见岗位:C++ / Qt 客户端

答案要点

  1. 多关键词匹配首选AC自动机:Trie加失败指针,一遍扫描文本找出全部命中
  2. 失败指针指向当前串最长真后缀对应的节点,用BFS按层构建
  3. 匹配复杂度约为O(文本长度+命中数),与关键词个数基本无关
  4. 逐词KMP或find的代价是关键词数×文本长度,关键词多时不可取
  5. 大字符集用哈希或双数组Trie节省内存,词表更新时后台重建再替换

易错点

面试官常见追问

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

相关面试题