KMP算法C++实现：详解与示例 |21xrx.com

KMP算法C++实现：详解与示例

2023-10-13 15:10:48 深夜i -- --

KMP算法 C++实现详解示例字符串匹配

KMP算法是一种字符串匹配算法，用于解决在一个主串中查找一个模式串的问题。其核心思想是利用已经匹配过的子串信息来尽量跳过不必要的比较，从而提高匹配效率。

下面我们将详细解释KMP算法的实现，并给出一个C++的示例。

首先，我们需要构建模式串的最长公共前后缀数组（即next数组）。这个数组记录了在模式串中，每个字符前面的子串中最长的相同前缀和后缀的长度。根据这个数组，我们可以在匹配过程中根据不同情况来选择合适的移动。

下面是构建next数组的过程：


void getNext(const string& pattern, vector<int>& next){
  int len = pattern.length();
  next[0] = -1;
  
  int i = 0, j = -1;
  while(i < len){
    if(j == -1 || pattern[i] == pattern[j]){
      i++;
      j++;
      next[i] = j;
    }else{
      j = next[j];
    }
  }
}

接下来，我们使用构建好的next数组进行匹配：


bool kmp(const string& text, const string& pattern){
  int n = text.length();
  int m = pattern.length();
  
  vector<int> next(m, 0);
  getNext(pattern, next);
  
  int i = 0, j = 0;
  while(i < n && j < m){
    if(j == -1 || text[i] == pattern[j]){
      i++;
      j++;
    }else{
      j = next[j];
    }
  }
  
  if(j == m)
    return true;
  
  return false;
}

以上就是KMP算法的具体实现。下面我们来看一个示例：


int main(){
  string text = "bababababa";
  string pattern = "aba";
  
  bool result = kmp(text, pattern);
  
  if(result)
    cout << "Pattern found in text" << endl;
  else
    cout << "Pattern not found in text" << endl;
  
  
  return 0;
}

以上代码中，我们在主串"bababababa"中查找模式串"aba"，如果模式串存在于主串中，则输出"Pattern found in text"，否则输出"Pattern not found in text"。

综上所述，KMP算法是一种高效的字符串匹配算法，通过构建模式串的最长公共前后缀数组，可以减少不必要的比较，提高匹配效率。通过以上示例，我们可以清楚地理解和实现KMP算法。

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

下一篇: 解决OpenCV存储大图耗时问题的方法

评论区

()

相似文章