字符串匹配算法：暴力匹配、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;
  // 初始化表数组，初始值都为0
  const table = new Array(n).fill(0);
  // 初始化指针i和j
  let 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