1. 先定义匹配单位
基础的计数和回文见数组与哈希、双指针与滑动窗口。本篇是主线之后的选学,先学朴素匹配,再学 KMP,最后根据前缀查询需求学习 Trie。
下面单模式匹配直接按 JavaScript 字符串的 UTF-16 代码单元比较并返回代码单元下标,与 indexOf 的定位单位一致;空模式返回 0,无匹配返回 -1。不会自动忽略大小写、做规范化或识别用户可见字素。输入均为字符串,不做隐式类型转换。
2. 朴素匹配:每个起点都尝试
function bruteForce(text, pattern) {
for (let start = 0; start <= text.length - pattern.length; start++) {
let j = 0;
while (j < pattern.length && text[start + j] === pattern[j]) j++;
if (j === pattern.length) return start;
}
return -1;
}每次固定起点,比较模式中的所有位置。模式比文本长时没有候选起点;空模式第一次就匹配。
设代码单元长度为 n 和 m,非空模式最坏时间为 O(nm),辅助空间为 O(1)。例如大量重复前缀会导致失败后反复比较相同位置。小输入时,这份简单实现有助于作为正确性对照。
3. KMP:利用已匹配前缀避免重来
3.1 前缀表的含义
lps[i] 表示模式前缀 [0, i] 中,最长的“既是前缀又是后缀”的真前缀长度,不允许整个前缀本身作为答案。例如模式 ababaca 的表为 [0, 0, 1, 2, 3, 0, 1]。
匹配时 j 表示已经匹配的模式长度。发生失配后,不需要把文本指针退回;已匹配后缀只有与模式前缀相同的部分可能继续参与匹配,因此把 j 退到 lps[j - 1],必要时重复回退。
function kmp(text, pattern) {
if (pattern.length === 0) return 0;
const lps = new Array(pattern.length).fill(0);
for (let i = 1, j = 0; i < pattern.length; i++) {
while (j > 0 && pattern[i] !== pattern[j]) j = lps[j - 1];
if (pattern[i] === pattern[j]) j++;
lps[i] = j;
}
for (let i = 0, j = 0; i < text.length; i++) {
while (j > 0 && text[i] !== pattern[j]) j = lps[j - 1];
if (text[i] === pattern[j]) j++;
if (j === pattern.length) return i - pattern.length + 1;
}
return -1;
}3.2 为什么不是两层循环的平方时间
外层指针只前进,匹配长度每次最多增加一;内层每次回退都严格减小匹配长度。回退总次数受总增长次数约束,因此建表为 O(m),扫描为 O(n),合计 O(n + m),辅助空间为 O(m)。
手推文本 abababaca 与模式 ababaca:说明失配时保留了哪个已匹配后缀。不要混用“前缀长度”和旧资料中“前缀末尾下标”的两套表定义。
4. Trie:多个单词共享前缀
字典树不是单文本中查找全部模式的完整算法,它首先解决存储词表、完整词查询和前缀查询。每条边代表一个字符,完整词结束标记可以位于内部节点,不能只用“是否叶子”判断。
本实现按 for...of 的 Unicode 代码点建边,不返回文本下标;与前面按代码单元定位的接口不同。空串可插入,空前缀查询恒为真;重复插入不会重复计数。
class TrieTree {
constructor() { this.root = { children: new Map(), end: false }; }
insert(text) {
let node = this.root;
for (const char of text) {
if (!node.children.has(char)) {
node.children.set(char, { children: new Map(), end: false });
}
node = node.children.get(char);
}
node.end = true;
}
walk(text) {
let node = this.root;
for (const char of text) {
node = node.children.get(char);
if (!node) return null;
}
return node;
}
find(text) { return this.walk(text)?.end === true; }
startsWith(text) { return this.walk(text) !== null; }
}设单词代码点长度为 L,在 Map 平均常数查询模型下,插入与查询时间为 O(L)。总节点数不超过所有插入词长度之和再加根节点,空间为 O(S + 1);查询自身只需常数辅助空间。前缀补全还需要枚举后代,成本要计入访问节点与返回文本,不能声称输出所有建议也只需前缀长度的时间。
5. 其他匹配算法如何选学
原文中重复且错误的 BM 示例不再作为可执行模板,保留其核心方法与边界;这些方法没有固定的普适速度排名。
| 方法 | 核心思想 | 适合研究的场景与限制 |
|---|---|---|
Rabin–Karp | 用滚动哈希快速筛选候选子串,再比较真实文本 | 哈希相等不证明文本相等;碰撞多时核对成本可退化为 O(nm),还要考虑模运算与整数精度 |
Boyer–Moore | 从模式尾部向前比较,用坏字符与好后缀规则跳过不可能起点 | 好后缀无完整再出现时还要考虑与模式前缀的部分重合;错误位移会漏解或倒退;成本依具体变体与输入而定 |
Aho–Corasick | 在词表字典树上增加失败链接和输出信息,一次扫描匹配多个模式 | 适合固定多模式词表;转移表示、字母表大小和输出数量影响构建/空间/运行成本,输出全部命中必须计费 |
BM 坏字符位移与好后缀位移需要结合,并保证每次至少前进一步;仅有坏字符规则不是完整的最坏线性保证。AC 的失败链接表示当前状态失配时可保留的最长词表前缀后缀,不能把它当作普通树的父指针。
后续练习可选:对词表 he、she、his、hers 画出共享前缀,再手推文本 ushers 的重叠命中;先验证 she、he 与 hers 都能找到,再考虑实现失败链接。
6. 验证与复习
node --test tests/algorithm-structures-examples.test.mjs朴素与 KMP 用小文本/模式穷举,与原生 indexOf 对照;包括空串、模式更长、重叠前缀与非基本平面字符。字典树检查完整词与前缀的区别、空串、重复插入与代码点处理。
闭卷追问:为什么 KMP 回退的是模式已匹配长度而不是文本指针?为什么插入 apple 不代表完整词 app 已经存在?答清楚再进阶到 BM 或 AC,不要求一次实现所有字符串算法。
评论
正在加载评论…