KMP算法C++代码：解决字符串匹配问题的高效算法 |21xrx.com

KMP算法C++代码：解决字符串匹配问题的高效算法

2024-05-13 04:55:10 深夜i -- --

KMP算法字符串匹配高效 C++代码

KMP算法是一种高效的字符串匹配算法，用于解决字符串匹配问题。它的代码实现采用C++编程语言。

字符串匹配问题是在一个字符串中查找是否存在子串的过程。传统的字符串匹配算法，如暴力匹配算法，是通过逐个比较来找到匹配的子串。然而，这种方法在某些情况下效率较低。例如，在一个长文本中查找一个短字符串时，暴力匹配算法的时间复杂度为O(n*m)，其中n是长文本的长度，m是短字符串的长度。如果文本和字符串长度很大，那么算法的执行时间将非常长。

KMP算法则通过利用已经匹配过的信息，跳过一部分比较操作，从而提高了搜索的效率。在KMP算法中，首先构建一个辅助数组（也称为失配函数）来记录前缀和后缀的最长匹配前缀长度。然后，用这个辅助数组来在匹配的过程中跳过不必要的比较，以减少时间复杂度。

以下是KMP算法的C++代码实现：


#include <iostream>
#include <vector>
using namespace std;
vector<int> constructLPS(string pattern) {
  int n = pattern.length();
  vector<int> lps(n, 0);
  int len = 0;
  int i = 1;
  while (i < n) {
    if (pattern[i] == pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    }
    else {
      if (len != 0) {
        len = lps[len - 1];
      }
      else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return lps;
}
void KMP(string text, string pattern) {
  int n = text.length();
  int m = pattern.length();
  vector<int> lps = constructLPS(pattern);
  int i = 0;
  int j = 0;
  while (i < n) {
    if (pattern[j] == text[i]) {
      i++;
      j++;
    }
    if (j == m) {
      cout << "Pattern found at index " << i - j << endl;
      j = lps[j - 1];
    }
    else if (i < n && pattern[j] != text[i]) {
      if (j != 0) {
        j = lps[j - 1];
      }
      else {
        i++;
      }
    }
  }
}
int main() {
  string text = "ABABDABACDABABCABAB";
  string pattern = "ABABCABAB";
  KMP(text, pattern);
  return 0;
}

上述代码中，构建LPS数组的函数constructLPS在字符串pattern上进行迭代，并通过比较字符来确定最长匹配前缀长度。KMP函数则使用LPS数组在字符串text上进行迭代，并在匹配成功时输出匹配的索引。

KMP算法的时间复杂度为O(n+m)，其中n和m分别是文本和字符串的长度。因此，KMP算法是一种高效的解决字符串匹配问题的算法。

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

下一篇: 使用OpenCV将Mat转为数组

评论区

()

相似文章