从兄弟单词面试题延伸：字符串检索工具箱——签名、Trie、KMP、AC 自动机怎么选

图 1：本文封面，四种工具各占一个象限。

「兄弟单词」这道经典面试题——把字母重排后相同的词聚成一组——用一张哈希表就能解：把每个单词的字母排序作为签名，签名相同的进同一桶。这道题值得记住的解法之外，还有一个更值得记住的问题：如果场景变一变，签名还管用吗？答案是不一定。字符串检索不是一把刀用到底，而是一整箱工具，选型的第一步是看清自己的场景落在哪个象限。

一个 2×2 象限，四种工具各就各位。

用两个维度给检索场景分类：查的是「整词/前缀」还是「子串」；模式是「单个」还是「一批」。四个象限各有一件最顺手的工具：

• 整词等价、单个模式：哈希签名。把「等价」编码成同一个键，判同 O(n)。兄弟单词就是典型——签名把字母序的差异抹掉，只留等价类。任何「定义一个等价关系，然后分组」的问题都能套这个模板。
• 整词/前缀、词表固定：Trie 前缀树。词表里共享的前缀合并成树的一条路径，查找耗时只跟词长有关，与词表规模无关。自动补全、输入法候选、路由表的最长前缀匹配，都是它的主场。
• 子串、单个模式：KMP。在文本里找一个模式串，用 next 数组记住「失配时已匹配前缀还能利用多少」，文本指针永不回退，预处理加匹配合计 O(n+m)。1977 年 Knuth、Morris、Pratt 联合发表的这篇论文，至今仍是单模式匹配的基准答案。
• 子串、一批模式：AC 自动机。1975 年 Aho 与 Corasick 提出，把一批模式串建成 Trie，再给每个节点接一条「失配指针」，文本只扫一遍就能命中全部模式，复杂度与文本长度、模式总长、命中次数成线性。敏感词过滤、入侵检测的特征匹配，靠的都是它——Unix 老牌命令 fgrep 的底子就是它。

象限边界处也有交叉：前缀检索做到极致可以压缩成 Radix Tree；多模式如果模式极少，跑几遍 KMP 也未必输。选型看的是主矛盾，不是信仰。

四种工具的最小实现，一次全跑通。

光说不练假把式。下面这份代码把四件工具各写一个最小可用版，并各自跑一个经典用例。用 Node.js 22.15.0 直接运行（node string-toolbox.js）：

'use strict';

// 工具 1：哈希签名 —— 字母排序作签名，兄弟单词自然聚到同一桶（O(n·k log k)）
const sig = (w) => [...w].sort().join('');
const words = ['listen', 'silent', 'enlist', 'hello', 'world'];
const groups = new Map();
for (const w of words) {
  const key = sig(w);
  groups.set(key, [...(groups.get(key) ?? []), w]);
}
console.log(`签名分组：${[...groups.values()].map((g) => g.join('/')).join('，')}`);

// 工具 2：Trie —— 共享前缀成树，查找耗时只与词长有关
function buildTrie(dict) {
  const root = { children: new Map(), end: false };
  for (const w of dict) {
    let node = root;
    for (const ch of w) {
      if (!node.children.has(ch)) node.children.set(ch, { children: new Map(), end: false });
      node = node.children.get(ch);
    }
    node.end = true;
  }
  return root;
}
function withPrefix(root, prefix) {
  let node = root;
  for (const ch of prefix) {
    if (!node.children.has(ch)) return [];
    node = node.children.get(ch);
  }
  const out = [];
  (function walk(n, path) {
    if (n.end) out.push(path);
    for (const [ch, child] of n.children) walk(child, path + ch);
  })(node, prefix);
  return out;
}
const trie = buildTrie(['apple', 'app', 'apply', 'apex']);
console.log(`Trie 前缀检索 "app" -> ${withPrefix(trie, 'app').join(', ')}`);

// 工具 3：KMP —— next 数组复用已匹配前缀，文本指针不回退，O(n+m)
function buildNext(p) {
  const next = [0];
  for (let i = 1, k = 0; i < p.length; i++) {
    while (k > 0 && p[i] !== p[k]) k = next[k - 1];
    if (p[i] === p[k]) k++;
    next[i] = k;
  }
  return next;
}
function kmp(text, pattern) {
  const next = buildNext(pattern);
  let hits = [];
  for (let i = 0, j = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = next[j - 1];
    if (text[i] === pattern[j]) j++;
    if (j === pattern.length) { hits.push(i - j + 1); j = next[j - 1]; }
  }
  return hits;
}
const text = 'ABC ABCDAB ABCDABCDABDE';
console.log(`KMP 在文本中找 "ABCDABD" -> 命中位置 ${kmp(text, 'ABCDABD').join(', ')}`);

// 工具 4：AC 自动机 —— Trie 加失配指针，一遍扫描命中全部模式
function buildAC(patterns) {
  const root = buildTrie(patterns);
  root.fail = root;
  const queue = [];
  for (const child of root.children.values()) { child.fail = root; queue.push(child); }
  while (queue.length) {
    const node = queue.shift();
    for (const [ch, child] of node.children) {
      let f = node.fail;
      while (f !== root && !f.children.has(ch)) f = f.fail;
      child.fail = f.children.get(ch) !== child && f.children.has(ch) ? f.children.get(ch) : root;
      if (child.fail.end) child.end = true;
      queue.push(child);
    }
  }
  return root;
}
function acScan(root, text, patterns) {
  const hits = [];
  let node = root;
  for (let i = 0; i < text.length; i++) {
    const ch = text[i];
    while (node !== root && !node.children.has(ch)) node = node.fail;
    node = node.children.get(ch) ?? root;
    if (node.end) for (const p of patterns) {
      if (i - p.length + 1 >= 0 && text.slice(i - p.length + 1, i + 1) === p) hits.push(`${p}@${i - p.length + 1}`);
    }
  }
  return hits;
}
const dict = ['he', 'she', 'his', 'hers'];
console.log(`AC 自动机扫描 "ushers" -> ${acScan(buildAC(dict), 'ushers', dict).join(', ')}`);

实测输出：

签名分组：listen/silent/enlist，hello，world
Trie 前缀检索 "app" -> app, apple, apply
KMP 在文本中找 "ABCDABD" -> 命中位置 15
AC 自动机扫描 "ushers" -> he@2, she@1, hers@2

四行输出各印证一件事：签名把三个兄弟单词聚进一桶；Trie 按前缀捞出三个候选词；KMP 在文本第 15 位命中目标，全程文本指针没回退；AC 自动机一遍扫过 ushers，把 she、he、hers 三个模式同时抓出来——「多模式一遍扫」就是它和「跑三遍 KMP」的本质差距。

图 2：四种工具的机制、复杂度与适用边界。

工程里的选型直觉。

做搜索框补全，词表百万级也首选 Trie 或其压缩变体，因为延迟只随用户键入长度涨；做内容安全的敏感词拦截，模式成千上万且要扫全量文本，AC 自动机几乎是不二之选；做单次日志检索，直接调语言内置的 indexOf 就行——多数语言内置实现已是优化过的串匹配，没必要手写 KMP；做「忽略顺序的等价判断」（验证码、乱序密码、题目查重），一行签名搞定。

这套象限图在 AI 工程里同样用得着：prompt 模板的前缀路由、检索词归一化、敏感词护栏，分别对应 Trie、签名与 AC 自动机三个象限。你在项目里用过哪种字符串检索结构？有没有遇到过「选错结构、上线才暴露性能问题」的教训？欢迎聊聊。