KMP算法C++实现 |21xrx.com

KMP算法C++实现

2023-08-03 22:32:27 深夜i -- --

KMP算法 C++ 字符串匹配前缀函数模式串

KMP算法是一种用于字符串匹配的高效算法。它是由James H. Morris、Donald R. Knuth和Vaughan Pratt三位计算机科学家共同提出的。KMP算法的全称是Knuth-Morris-Pratt算法，其核心思想是利用已经匹配过的前缀来避免不必要的回溯，从而提高匹配效率。

在传统的字符串匹配算法中，我们会从主串的每个字符开始，逐个与模式串进行比较。如果发现字符不匹配，会回溯到主串的下一个字符继续匹配，这种做法十分耗时。而KMP算法通过提前计算模式串中的某些信息，可以在匹配过程中避免不必要的回溯，从而加快匹配速度。

KMP算法的核心是构建模式串的最长公共前缀后缀数组，称为next数组。next数组的主要作用是告诉我们，当某一位字符不匹配时，模式串应该移动到哪个位置继续匹配。通过避免回溯，我们可以跳过一些已经比较过的字符，大大提高匹配效率。

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


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

这段代码中，我们首先使用`getNext`函数来构建模式串的next数组。然后，我们使用两个指针`i`和`j`来分别指向主串和模式串中的字符。在匹配过程中，如果当前字符匹配成功，我们将两个指针都向后移动一位；如果不匹配，我们根据next数组的值来决定模式串的移动位置。

在上述例子中，我们在主串"ABCABCDABABCDABCDABDE"中查找模式串"ABCDABD"的位置。运行结果表明，模式串在主串中的索引为11，也就是说模式串在主串中第一次出现的位置是从索引11开始。

通过KMP算法，我们可以高效地解决字符串匹配问题。它的时间复杂度为O(m+n)，其中m和n分别为主串和模式串的长度。相比传统的匹配算法，KMP算法对于大规模字符串匹配问题具有很大的优势。

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

下一篇: 如何安装FFmpeg

评论区

()

相似文章