前端工程师的 LeetCode 之旅 -- KMP 字符串匹配算法（修正版）

字符串匹配算法在前端开发中有着广泛的应用，例如处理用户输入、优化网页加载速度等。KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它的核心思想是利用已经匹配失败的信息，避免不必要的比较，从而提高匹配效率。

KMP 算法的核心在于构建一个“部分匹配表”（Partial Match Table），也称为“失败函数”（Fail Function）。该表记录了每个前缀的最长后缀的长度，用于在匹配失败时跳过不必要的比较。通过这个表，我们可以快速定位到下一个可能的比较位置，从而减少比较次数。

下面是一个简单的 KMP 算法实现：

function kmpSearch(pattern, text) {
  const m = pattern.length;
  const n = text.length;
  const lps = new Array(m).fill(0); // 构建部分匹配表
  let j = 0; // 当前匹配位置
  let i = 1; // 当前比较位置
  while (i < m) {
    if (pattern[i] === pattern[j]) {
      j++;
      lps[i] = j;
      i++;
    } else {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  let p = 0; // 当前匹配位置
  while (p < m && i < n) {
    if (pattern[p] === text[i]) {
      p++;
      i++;
    } else {
      if (p !== 0) {
        p = lps[p - 1];
      } else {
        i++;
      }
    }
  }
  if (p === m) {
    return i - p; // 返回匹配子串在文本中的起始位置
  } else {
    return -1; // 没有找到匹配的子串
  }
}

这个实现中，我们首先构建了一个长度为 m 的部分匹配表 lps，其中 m 是模式串的长度。然后，我们使用双指针法在模式串和文本中进行匹配。当模式串中的字符与文本中的字符不匹配时，我们根据部分匹配表中的值来更新指针位置，避免不必要的比较。最后，如果找到了匹配的子串，我们返回其在文本中的起始位置；否则，返回 -1。

需要注意的是，KMP 算法的时间复杂度为 O(n+m)，其中 n 是文本的长度，m 是模式串的长度。因此，对于较长的文本和模式串，KMP 算法具有较好的性能表现。在实际应用中，我们可以根据具体的需求选择适合的字符串匹配算法。

通过理解 KMP 算法的实现原理和应用场景，前端工程师可以更好地应对各种字符串处理问题，提高代码效率和性能。同时，掌握 KMP 算法也可以为解决复杂问题提供新的思路和方法。