C++实现KMP算法: 一个高效的字符串匹配算法 |21xrx.com

C++实现KMP算法: 一个高效的字符串匹配算法

2023-08-06 21:35:38 深夜i -- --

C++ KMP算法字符串匹配高效实现

C++实现KMP算法：一个高效的字符串匹配算法

字符串匹配算法在计算机科学中有广泛的应用。其中，KMP算法是一种高效的字符串匹配算法。它可以在O(n+m)的时间复杂度内查找模式串在目标串中的出现位置，其中n和m分别为目标串和模式串的长度。本文将探讨使用C++实现KMP算法的步骤和优势。

KMP算法的核心思想是通过预处理模式串，构建一个部分匹配表（Partial Match Table，简称PMT），利用部分匹配表中的信息，来尽量减少目标串与模式串的比较次数。通过这种方式，KMP算法相比于暴力匹配算法具有更高的效率。

下面是使用C++实现KMP算法的步骤：

1. 构建部分匹配表（PMT）：

- 遍历模式串，从左到右，依次计算每个位置的最长公共前后缀的长度。

- 在每个位置i处，计算模式串的前缀和后缀的重叠最大长度，即PMT[i]。

- PMT[i]表示模式串中以i结尾的子串（包括i）的最长公共前后缀的长度。

2. 利用部分匹配表进行匹配：

- 在目标串中，设置两个指针i和j，分别指向当前比较的位置。

- 当目标串的第i个字符和模式串的第j个字符匹配时，同时移动i和j。

- 如果目标串的第i个字符和模式串的第j个字符不匹配，根据部分匹配表来决定模式串指针j的移动。

- 如果j等于0，表示模式串的第一个字符不匹配，令i移动到下一个位置。

- 如果j大于0，用部分匹配表中j-1的值来更新j，即j = PMT[j-1]。

通过以上步骤，可以实现一个高效的KMP算法。与暴力匹配算法相比，KMP算法减少了无效的比较操作，提高了匹配效率。在处理大规模文本搜索、模式匹配等问题时，KMP算法更具实用性。

C++语言的强大性能和丰富的库函数使其成为实现KMP算法的理想选择。下面是一个简单的C++代码示例：


#include <iostream>
#include <vector>
// 构建部分匹配表
std::vector<int> buildPMT(const std::string& pattern) {
  std::vector<int> PMT(pattern.length(), 0);
  int maxLength = 0;
  for (int i = 1; i < pattern.length(); i++) {
    while (maxLength > 0 && pattern[i] != pattern[maxLength]) {
      maxLength = PMT[maxLength - 1];
    }
    if (pattern[i] == pattern[maxLength]) {
      maxLength++;
    }
    PMT[i] = maxLength;
  }
  return PMT;
}
// KMP算法
std::vector<int> KMP(const std::string& target, const std::string& pattern) {
  std::vector<int> PMT = buildPMT(pattern);
  std::vector<int> matchedIndices;
  int j = 0;
  for (int i = 0; i < target.length(); i++) {
    while (j > 0 && target[i] != pattern[j]) {
      j = PMT[j - 1];
    }
    if (target[i] == pattern[j]) {
      j++;
    }
    if (j == pattern.length()) {
      matchedIndices.push_back(i - j + 1);
      j = PMT[j - 1];
    }
  }
  return matchedIndices;
}
int main() {
  std::string target = "ABCDABDABCDABCDABDE";
  std::string pattern = "ABCDABD";
  std::vector<int> matchedIndices = KMP(target, pattern);
  std::cout << "匹配位置：";
  for (int i = 0; i < matchedIndices.size(); i++) {
    std::cout << matchedIndices[i] << " ";
  }
  std::cout << std::endl;
  return 0;
}

以上示例代码将输出匹配位置：0 9。表示模式串在目标串中的出现位置。

综上所述，KMP算法是一种高效的字符串匹配算法，通过预处理模式串构建部分匹配表，可以在O(n+m)的时间复杂度内查找模式串在目标串中的出现位置。利用C++的性能和库函数，我们可以轻松实现KMP算法，并解决实际的字符串匹配问题。

上一篇: idea打包java可执行jar包

下一篇: 推流至rtmp服务器的ffmpeg代码

评论区

()

相似文章