字符串匹配算法完全指南 🔍
一、KMP算法：高效的字符串匹配
1. 为什么需要KMP？ 🤔
想象你在一个很长的文章中查找一个单词，普通的方法是一个字符一个字符地比较。但如果匹配失败，我们往往要回退很多位置重新开始。这样效率很低！
KMP算法就是为了解决这个问题，它能够避免不必要的回退，大大提高匹配效率。
2. 核心思想 💡
KMP的关键在于：当匹配失败时，我们已经知道了一些信息，可以利用这些信息避免回退。
举个例子：
文本串： hello world
模式串： world
↑
当这里匹配失败时，我们不需要完全回退3. 代码实现
3.1 构建next数组（最关键的部分）
js
function getNext(pattern) {
const next = new Array(pattern.length).fill(0);
next[0] = -1; // 第一个字符失配时，模式串向右移动一位
let i = 1; // 当前位置
let j = 0; // 最长相同前后缀长度
while (i < pattern.length) {
if (pattern[i] === pattern[j]) {
// 字符相同，前后缀长度加1
next[i] = j;
i++;
j++;
} else if (j > 0) {
// 字符不同，缩短前缀长度
j = next[j];
} else {
// j已经退到开头，无法再缩短
next[i] = 0;
i++;
}
}
return next;
}3.2 KMP搜索
js
function kmpSearch(text, pattern) {
if (!pattern || pattern.length === 0) return 0;
const next = getNext(pattern);
let i = 0; // 文本串指针
let j = 0; // 模式串指针
while (i < text.length && j < pattern.length) {
if (text[i] === pattern[j]) {
// 字符匹配，两个指针都向前移动
i++;
j++;
} else if (next[j] === -1) {
// 模式串第一个字符就不匹配
i++;
} else {
// 根据next数组移动模式串指针
j = next[j];
}
}
// 如果模式串完全匹配，返回匹配起始位置
return j === pattern.length ? i - j : -1;
}4. 实际应用示例 🌟
js
// 在文本编辑器中查找关键词
function findKeyword(content, keyword) {
const index = kmpSearch(content, keyword);
if (index !== -1) {
console.log(`找到关键词！位置在: ${index}`);
// 高亮显示关键词
return content.slice(0, index) +
`<span class="highlight">${keyword}</span>` +
content.slice(index + keyword.length);
}
return '未找到关键词';
}
// 使用示例
const content = "这是一篇很长的文章，我们要在其中查找某个关键词...";
const keyword = "关键词";
console.log(findKeyword(content, keyword));二、Manacher算法：寻找最长回文子串
1. 什么是回文串？ 🔄
回文串就是正着读和倒着读都一样的字符串，比如：
- "level"
- "上海自来水来自海上"
2. 算法原理
2.1 预处理
为了统一处理奇数和偶数长度的回文串，我们在字符间插入特殊字符：
js
// 原串： level
// 处理后：#l#e#v#e#l#js
function preProcess(s) {
return '#' + s.split('').join('#') + '#';
}2.2 核心算法
js
function manacher(s) {
const str = preProcess(s);
const p = new Array(str.length).fill(0); // 回文半径数组
let center = 0; // 当前中心
let maxRight = 0; // 当前最右边界
for (let i = 0; i < str.length; i++) {
if (i < maxRight) {
// 利用对称性
const mirror = 2 * center - i;
p[i] = Math.min(maxRight - i, p[mirror]);
}
// 尝试扩展回文
let left = i - (1 + p[i]);
let right = i + (1 + p[i]);
while (left >= 0 && right < str.length && str[left] === str[right]) {
p[i]++;
left--;
right++;
}
// 更新中心和右边界
if (i + p[i] > maxRight) {
center = i;
maxRight = i + p[i];
}
}
// 找到最长回文子串
let maxLen = 0;
let centerIndex = 0;
for (let i = 0; i < p.length; i++) {
if (p[i] > maxLen) {
maxLen = p[i];
centerIndex = i;
}
}
// 还原原始字符串中的回文子串
const start = Math.floor((centerIndex - maxLen) / 2);
return s.substring(start, start + maxLen);
}3. 使用示例 ⭐
js
// 查找最长回文子串
const text = "babadada";
console.log(manacher(text)); // "adada"
// 实际应用：检查文本是否对称
function isSymmetric(text) {
const longest = manacher(text);
return longest.length === text.length;
}
console.log(isSymmetric("level")); // true
console.log(isSymmetric("hello")); // false三、性能对比 📊
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 朴素匹配 | O(mn) | O(1) | 短文本匹配 |
| KMP | O(m+n) | O(m) | 长文本搜索 |
| Manacher | O(n) | O(n) | 回文串查找 |
四、实践建议 💡
- 对于简单的字符串匹配，可以使用内置的
indexOf()方法 - 需要高效的模式匹配时，使用KMP算法
- 查找回文串时，Manacher算法是最佳选择
- 注意边界情况的处理