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

C++ KMP算法实现

2023-08-06 03:18:23 深夜i -- --

C++ KMP算法实现

KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，用于在一个文本串S内查找一个模式串P是否出现。相比于暴力匹配算法，KMP算法的时间复杂度为O(n+m)，其中n为文本串的长度，m为模式串的长度，是一种高效的匹配算法。

KMP算法的实现主要依赖于构建模式串的next数组。next数组用于记录模式串中每个字符对应的最长公共前后缀的长度。这样在匹配失败时，我们可以通过next数组快速移动模式串的起始位置，而不需要回溯到起始位置重新匹配。

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


#include <iostream>
#include <vector>
using namespace std;
vector<int> getNext(string p){
  vector<int> next(p.size(), 0);
  int j = 0;
  for(int i = 1; i < p.size(); i++){
    while(j > 0 && p[i] != p[j]){
      j = next[j-1];
    }
    if(p[i] == p[j]){
      j++;
    }
    next[i] = j;
  }
  return next;
}
int kmp(string s, string p){
  vector<int> next = getNext(p);
  int j = 0;
  for(int i = 0; i < s.size(); i++){
    while(j > 0 && s[i] != p[j]){
      j = next[j-1];
    }
    if(s[i] == p[j]){
      j++;
    }
    if(j == p.size()){
      return i - j + 1; // 匹配成功，返回起始位置
    }
  }
  return -1; // 匹配失败
}
int main(){
  string s = "ABCABDABABCABCDABDE";
  string p = "ABCABCDABD";
  int result = kmp(s, p);
  if(result != -1){
    cout << "模式串出现的位置是：" << result << endl;
  }else{
    cout << "模式串未出现" << endl;
  }
  return 0;
}

在上述示例代码中，getNext函数用于构建next数组，kmp函数用于进行模式串的匹配。在主函数中，我们可以根据返回的匹配结果输出相应的结果。

总的来说，KMP算法是一种高效的字符串匹配算法，在实际应用中有着广泛的应用场景。通过构建next数组，我们可以快速移动模式串的起始位置，提高匹配效率。通过掌握KMP算法的实现原理和代码实现，我们可以更好地理解算法的内部机制，并能更加灵活地应用于实际开发中。

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

下一篇: 使用VS2013进行人脸识别的方法及步骤

评论区

()

相似文章