C++ KMP算法代码详解及示例 |21xrx.com

C++ KMP算法代码详解及示例

2023-09-23 12:10:36 深夜i -- --

C++ KMP算法代码详解示例

KMP算法，全称为Knuth-Morris-Pratt算法，是一种字符串匹配算法。它的目的是在一个长文本串S中查找一个较短的模式串P的出现位置。

KMP算法的核心思想是通过利用已经匹配过的字符部分，减少不必要的字符比较次数。它的实现基于两个指针，一个指向文本串S的当前字符，一个指向模式串P的当前字符。在匹配过程中，如果当前字符不匹配，算法将根据已经匹配的前缀字符的匹配情况，决定如何移动模式串的指针，从而跳过已经匹配的部分。

KMP算法的核心思想可以通过一个next数组来实现。next数组保存了模式串中每个字符对应的最长匹配前缀的长度。通过next数组，KMP算法可以根据当前字符的匹配情况，决定如何移动模式串的指针。

接下来让我们看一个具体的实现示例：


#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<int> getNext(const string& pattern) {
  int m = pattern.size();
  vector<int> next(m, 0);
  int i = 1, j = 0;
  while (i < m) {
    if (pattern[i] == pattern[j]) {
      next[i++] = ++j;
    }
    else {
      if (j > 0) {
        j = next[j - 1];
      }
      else {
        next[i++] = 0;
      }
    }
  }
  return next;
}
int kmp(const string& text, const string& pattern) {
  int n = text.size();
  int m = pattern.size();
  vector<int> next = getNext(pattern);
  int i = 0, j = 0;
  while (i < n) {
    if (text[i] == pattern[j]) {
      i++;
      j++;
      if (j == m)
        return i - m;
      
    }
    else {
      if (j > 0) {
        j = next[j - 1];
      }
      else {
        i++;
      }
    }
  }
  return -1;
}
int main() {
  string text = "ABCABDABACDABABCABAB";
  string pattern = "ABABCABAB";
  int pos = kmp(text, pattern);
  if (pos == -1)
    cout << "Pattern not found in text." << endl;
  
  else
    cout << "Pattern found at position " << pos << " in text." << endl;
  
  return 0;
}

在这个示例中，我们定义了两个函数：`getNext`和`kmp`。`getNext`函数用于计算模式串对应的next数组，`kmp`函数使用next数组进行匹配操作。

我们可以看到，在主函数中我们定义了一个文本串和一个模式串，并调用`kmp`函数进行匹配。如果模式串存在于文本串中，`kmp`函数将返回模式串在文本串中第一次出现的位置；如果模式串不存在于文本串中，`kmp`函数将返回-1。

通过理解KMP算法的核心思想以及代码示例，我们可以更好地理解这一算法的工作原理和实现方式。在实际应用中，KMP算法能够快速有效地解决字符串匹配问题，节省了不必要的比较次数，提高了匹配效率。

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

下一篇: FFmpeg HEVC解码：一步了解高效视频编解码技术

评论区

()

相似文章