字符串算法是程序员经常碰到的领域 —— 文本搜索、模糊匹配、拼写检查、DNA 序列分析。但很多人对它的认识停留在 indexOf。真正的字符串算法精彩得多:KMP 让你跳过重复匹配,Manacher 在 O(n) 求最长回文,后缀数组让任意子串查询 O(log n)。这篇文章把核心字符串算法讲透。
朴素字符串匹配
找 pattern 在 text 中的位置。最朴素:逐位置尝试。
function naiveSearch(text, pattern) {
for (let i = 0; i <= text.length - pattern.length; i++) {
let match = true;
for (let j = 0; j < pattern.length; j++) {
if (text[i + j] !== pattern[j]) { match = false; break; }
}
if (match) return i;
}
return -1;
}
// 复杂度 O(n*m),最坏情况 text = "aaaa...aab",pattern = "aab"KMP 算法
核心思想:匹配失败时,利用已匹配的信息跳过一些位置,不必回到 text 开始。
// 构建 next 数组:next[i] 表示 pattern[0..i] 的最长真前缀和真后缀的长度
function buildNext(pattern) {
const next = new Array(pattern.length).fill(0);
let j = 0;
for (let i = 1; i < pattern.length; i++) {
while (j > 0 && pattern[i] !== pattern[j]) j = next[j - 1];
if (pattern[i] === pattern[j]) j++;
next[i] = j;
}
return next;
}
function kmp(text, pattern) {
const next = buildNext(pattern);
let j = 0;
for (let i = 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) {
return i - j + 1; // 找到匹配位置
}
}
return -1;
}KMP 把复杂度从 O(n*m) 降到 O(n+m)。grep 早期实现就用 KMP。
Boyer-Moore
从 pattern 的末尾往前比,匹配失败时根据"坏字符"和"好后缀"规则跳过更多位置。实际比 KMP 更快(每步可能跳过 m 个字符,而不是 1 个)。
grep、Java String.indexOf 等成熟实现用 Boyer-Moore-Horspool(简化版)。
Rabin-Karp:哈希匹配
思路:计算 pattern 的哈希,然后在 text 上滚动哈希,哈希匹配时再实际比对。
function rabinKarp(text, pattern) {
const m = pattern.length, n = text.length;
const base = 31, mod = 1e9 + 7;
let patternHash = 0, textHash = 0, power = 1;
for (let i = 0; i < m; i++) {
patternHash = (patternHash * base + pattern.charCodeAt(i)) % mod;
textHash = (textHash * base + text.charCodeAt(i)) % mod;
if (i < m - 1) power = (power * base) % mod;
}
for (let i = 0; i <= n - m; i++) {
if (textHash === patternHash && text.slice(i, i + m) === pattern) {
return i;
}
if (i < n - m) {
textHash = ((textHash - text.charCodeAt(i) * power) * base + text.charCodeAt(i + m)) % mod;
if (textHash < 0) textHash += mod;
}
}
return -1;
}Rabin-Karp 的优势:多模式匹配(同时找多个 pattern)。哈希集合一次匹配 N 个 pattern。
Aho-Corasick:多模式匹配
Trie + KMP 的组合。一次扫描 text 找出所有 pattern 的所有出现。复杂度 O(n + m + k),k 是匹配数。
应用:敏感词过滤、入侵检测、广告过滤。nginx、Snort 内部都用。
Manacher:最长回文子串
朴素 O(n²),Manacher 算法 O(n)。核心思想:利用回文的对称性,已知 a 是 b 的回文中心时,b 内部的回文长度可以推导。
function manacher(s) {
// 预处理:在每个字符两边插 #,统一奇偶长度回文
const t = '#' + s.split('').join('#') + '#';
const p = new Array(t.length).fill(0);
let center = 0, right = 0;
let maxLen = 0, maxCenter = 0;
for (let i = 0; i < t.length; i++) {
const mirror = 2 * center - i;
if (i < right) p[i] = Math.min(right - i, p[mirror]);
while (i + p[i] + 1 < t.length &&
i - p[i] - 1 >= 0 &&
t[i + p[i] + 1] === t[i - p[i] - 1]) {
p[i]++;
}
if (i + p[i] > right) { center = i; right = i + p[i]; }
if (p[i] > maxLen) { maxLen = p[i]; maxCenter = i; }
}
const start = (maxCenter - maxLen) / 2;
return s.substr(start, maxLen);
}后缀数组(Suffix Array)
一个字符串所有后缀按字典序排序后的索引数组。应用:
- 任意子串查询 O(m log n)。
- 最长公共子串(多串)。
- 生物信息学序列分析。
function suffixArray(s) {
const n = s.length;
const sa = Array.from({length: n}, (_, i) => i);
sa.sort((a, b) => s.slice(a).localeCompare(s.slice(b)));
return sa;
}
// O(n log² n) 的优化版本用倍增排序,O(n log n) 用 SA-IS 算法后缀数组 + LCP(最长公共前缀)数组配合,几乎所有字符串问题都能解。
编辑距离(Levenshtein)
把字符串 A 改成 B 最少需要多少次操作(插/删/改)。经典动态规划。详见之前算法 DP 文章。
应用:拼写检查、DNA 比对、Diff 算法、模糊搜索。
Boyer-Moore vs KMP vs Rabin-Karp 选型
场景 推荐
单 pattern 大文本搜索 Boyer-Moore(实际最快)
教学 / 不要回退 KMP(理论清晰)
多 pattern 同时搜 Aho-Corasick
任意子串频繁查询 后缀数组 / 后缀树
模糊匹配 / 相似度 编辑距离正则表达式 vs 字符串算法
正则比专门算法更通用,但单一固定模式时慢。grep -F(fixed string)模式跳过正则引擎,用 Boyer-Moore,比正则快几倍。
大规模搜索的工程方案
- Elasticsearch / Solr:倒排索引 + BM25 评分,适合"关键词搜索"。
- Lucene:ES / Solr 底层。
- ripgrep:命令行的 grep 替代,极致优化的字符串搜索。
- Hyperscan:Intel 的高性能正则匹配库,网络入侵检测系统用。
写在最后
字符串算法看似"学术",但日常工程里到处用到 —— 你用 IDE 的全文搜索、用 grep、用日志分析、用浏览器 Find,背后都是这些算法。理解它们的复杂度和适用场景,能让你做出更好的工具选择,且面试时也能脱口而出。
一图看懂
KMP 状态机一图看懂:
—— 别看了 · 2026