字符串匹配算法：暴力匹配、KMP 算法、Boyer-Moore 算法、Rabin-Karp 算法

字符串匹配算法

字符串匹配算法是在一个字符串（称为文本）中查找另一个字符串（称为模式）出现的位置或者是否存在的算法。常见的字符串匹配算法包括暴力匹配、KMP算法、Boyer-Moore算法和Rabin-Karp算法。下面是对这些算法的简要介绍：

暴力匹配（Brute Force）算法：

• 算法原理：暴力匹配算法是最简单的一种字符串匹配算法。它的原理是从文本的每一个可能的位置开始，依次比较文本中的子串与模式串是否匹配。如果匹配成功，则返回匹配的位置；否则，继续尝试下一个位置。
• 时间复杂度：平均情况下为O(m*n)，其中m为文本长度，n为模式长度。
• 优点：
  • 算法简单易懂，容易实现。
  • 不需要额外的预处理步骤。
• 缺点：
  • 效率较低，时间复杂度为O(m*n)，其中m为文本长度，n为模式长度。
  • 对于大规模文本和模式，性能较差。

代码示例：

/*** 暴力匹配算法** @param text 目标文本* @param pattern 匹配模式* @returns 返回匹配模式在目标文本中的起始位置，如果没有找到匹配则返回-1*/
function bruteForce(text, pattern) {const m = text.length;const n = pattern.length;// 遍历文本串，查找模式串for (let i = 0; i <= m - n; i++) {let j = 0;// 逐个比较文本串和模式串的字符while (j < n && text[i + j] === pattern[j]) {j++;}// 如果模式串全部匹配成功if (j === n) {return i; // 返回匹配的起始位置}}// 没有找到匹配return -1; // 没有找到匹配
}// 示例用法
const text = "hello world";
const pattern = "world";
console.log(bruteForce(text, pattern)); // 输出: 6

KMP（Knuth-Morris-Pratt）算法：

• 算法原理：KMP算法通过预处理模式串构建部分匹配表（也称为next数组），然后在匹配过程中根据部分匹配表来移动模式串，避免重复比较已经匹配的部分。
• 时间复杂度：O(m+n)，其中m为文本长度，n为模式长度。
• 优点：
  • 在大多数情况下，时间复杂度为O(m+n)，具有较高的效率。
  • 通过部分匹配表避免了不必要的比较，提高了搜索速度。
• 缺点：
  • 实现较为复杂，需要构建部分匹配表。
  • 在特定情况下，性能可能不如其他算法。

代码示例：

/*** 生成KMP算法中的部分匹配表** @param pattern 待匹配的字符串* @returns 返回部分匹配表*/
function kmpTable(pattern) {// 获取模式串的长度const n = pattern.length;// 初始化表数组，初始值都为0const table = new Array(n).fill(0);// 初始化指针i和jlet i = 1, j = 0;// 当i小于n时，循环执行以下操作while (i < n) {// 如果模式串的第i个字符与第j个字符相等if (pattern[i] === pattern[j]) {// j指针向后移动一位j++;// 将j的值赋给表数组的第i个位置table[i] = j;// i指针向后移动一位i++;// 如果j大于0} else if (j > 0) {// 将j的值更新为表数组的第j-1个位置的值j = table[j - 1];// 如果j等于0} else {// i指针向后移动一位i++;}}// 返回表数组return table;
}/*** 使用KMP算法在文本中搜索模式串** @param text 文本* @param pattern 模式串* @returns 返回模式串在文本中的起始位置，如果未找到则返回-1*/
function kmpSearch(text, pattern) {const m = text.length;const n = pattern.length;if (n === 0) {return 0;}// 生成部分匹配表const table = kmpTable(pattern);let i = 0, j = 0;while (i < m) {// 如果当前字符匹配成功if (text[i] === pattern[j]) {i++;j++;// 如果已经匹配完整个模式串if (j === n) {return i - n; // 返回匹配的起始位置}// 如果当前字符匹配失败，且模式串的下一个字符不是第一个字符} else if (j > 0) {// 根据部分匹配表进行跳转j = table[j - 1];// 如果当前字符匹配失败，且模式串的下一个字符是第一个字符} else {i++;}}// 没有找到匹配return -1; // 没有找到匹配
}// 示例用法
const text = "hello world";
const pattern = "world";
console.log(kmpSearch(text, pattern)); // 输出: 6

Boyer-Moore算法：

• 算法原理：Boyer-Moore算法是一种启发式的字符串匹配算法，它利用了模式串中的信息来尽可能地跳过不必要的比较。主要有两种启发式规则：坏字符规则和好后缀规则。
• 时间复杂度：最坏情况下为O(m*n)，但平均情况下具有较高的效率。
• 优点：
  • 在实际应用中通常具有较高的效率，尤其是在模式串较长、字符集较大的情况下。
  • 利用了启发式规则，能够快速跳过不匹配的位置，减少比较次数。
• 缺点：
  • 实现相对复杂，需要理解和实现坏字符规则和好后缀规则。
  • 在某些情况下，性能可能不如其他算法。

代码示例：

/*** Boyer-Moore 字符串匹配算法** @param text 待匹配的文本* @param pattern 待匹配的模式* @returns 返回匹配到的起始位置，若未找到则返回-1*/
function boyerMoore(text, pattern) {const m = text.length;const n = pattern.length;if (n === 0) {return 0;}// 构建字符最后出现位置的映射const skip = {};for (let i = 0; i < n - 1; i++) {skip[pattern[i]] = n - i - 1;}skip[pattern[n - 1]] = n;let i = 0;while (i <= m - n) {let j = n - 1;// 从后往前匹配文本和模式while (j >= 0 && text[i + j] === pattern[j]) {j--;}if (j === -1) {return i; // 如果全部匹配成功，返回匹配的起始位置}// 根据字符最后出现位置的映射计算下一个匹配位置i += skip[text[i + n - 1]] || n;}return -1; // 没有找到匹配
}// 示例用法
const text = "hello world";
const pattern = "world";
console.log(boyerMoore(text, pattern)); // 输出: 6

Rabin-Karp算法：

• 算法原理：Rabin-Karp算法利用哈希函数来对模式串和文本中的子串进行哈希计算，然后比较哈希值来确定是否匹配。它适用于在一段文本中搜索多个不同的模式串。
• 时间复杂度：平均情况下为O(m+n)，其中m为文本长度，n为模式长度。
• 优点：
  • 在多个模式串匹配和字符串搜索中具有良好的性能。
  • 利用哈希函数实现了快速的模式匹配。
• 缺点：
  • 对于哈希冲突的处理和哈希函数的设计需要注意，影响算法的准确性和性能。
  • 在某些情况下，哈希函数的计算可能会造成额外的开销。

代码示例：

/*** Rabin-Karp 字符串匹配算法** @param text 文本字符串* @param pattern 模式字符串* @returns 返回模式字符串在文本字符串中首次出现的位置，若未找到则返回 -1*/
function rabinKarp(text, pattern) {const m = text.length;const n = pattern.length;if (n === 0) {return 0;}// 字符集大小const d = 256; // 字符集大小// 一个质数const q = 101; // 一个质数let p = 0, t = 0, h = 1;// 计算哈希值的基础值for (let i = 0; i < n - 1; i++) {h = (h * d) % q;}// 计算模式串和文本串的哈希值for (let i = 0; i < n; i++) {p = (d * p + pattern.charCodeAt(i)) % q;t = (d * t + text.charCodeAt(i)) % q;}// 遍历文本串，查找匹配for (let i = 0; i <= m - n; i++) {// 哈希值相等且字符串相等时，返回匹配的起始位置if (p === t && text.substring(i, i + n) === pattern) {return i; // 返回匹配的起始位置}// 更新文本串的哈希值if (i < m - n) {t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + n)) % q;if (t < 0) {t += q;}}}// 没有找到匹配return -1; // 没有找到匹配
}// 示例用法
const text = "hello world";
const pattern = "world";
console.log(rabinKarp(text, pattern)); // 输出: 6