KMP算法的C++代码 |21xrx.com

KMP算法的C++代码

2023-10-07 04:41:37 深夜i -- --

KMP算法 C++代码

KMP算法是一种字符串匹配算法，用于在一个长字符串中查找一个短字符串的出现位置。该算法通过利用短字符串的部分匹配信息，避免了不必要的比较操作，从而提高了匹配的效率。

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


#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 构建部分匹配表
vector<int> buildPartialMatchTable(const string& pattern) {
  int m = pattern.length();
  vector<int> table(m, 0);
  int j = 0;
  for (int i = 1; i < m; i++) {
    if (pattern[i] == pattern[j]) {
      table[i] = j + 1;
      j++;
    }
    else {
      if (j != 0) {
        j = table[j - 1];
        i--;
      }
      else {
        table[i] = 0;
      }
    }
  }
  return table;
}
// KMP算法
int kmpSearch(const string& text, const string& pattern) {
  int n = text.length();
  int m = pattern.length();
  vector<int> table = buildPartialMatchTable(pattern);
  int i = 0, j = 0;
  while (i < n) {
    if (text[i] == pattern[j]) {
      i++;
      j++;
      if (j == m)
        return i - j;
      
    } else {
      if (j != 0) {
        j = table[j - 1];
      } else {
        i++;
      }
    }
  }
  return -1;
}
int main() {
  string text = "ABCABCABD";
  string pattern = "ABCABD";
  int position = kmpSearch(text, pattern);
  if (position != -1)
    cout << "Pattern found at position: " << position << endl;
   else
    cout << "Pattern not found." << endl;
  
  return 0;
}

在上面的代码中，首先定义了两个函数：`buildPartialMatchTable`和`kmpSearch`。`buildPartialMatchTable`函数用于构建短字符串的部分匹配表，该表记录了在每一个位置上的最长前缀后缀相等子串的长度。`kmpSearch`函数则是KMP算法的核心实现，它利用部分匹配表来确定每次不匹配时的下一次比较位置。

在`main`函数中，我们定义了一个长字符串和一个短字符串，并调用`kmpSearch`函数来搜索短字符串在长字符串中的出现位置。如果找到了匹配位置，则输出该位置；否则输出未找到的提示信息。

KMP算法通过利用短字符串的部分匹配信息，避免了不必要的比较操作，从而提高了字符串匹配的效率。这个C++实现代码可以帮助我们更好地理解KMP算法的原理和实现方式，并在实际应用中提供了一种高效的字符串匹配方法。

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

下一篇: FFmpeg：PTS减去起始时间

评论区

()

相似文章