C++ 字符串匹配技巧 |21xrx.com

C++ 字符串匹配技巧

2023-07-02 15:41:52 深夜i -- --

C++ 字符串匹配技巧算法

C++作为一门高级语言，在字符串匹配方面也有着很强的表现力。下面就介绍几种C++字符串匹配技巧。

一、暴力匹配

暴力匹配是最原始的字符串匹配方式，使用一个循环依次比较模式串和文本串的每个字符，直到匹配成功或遍历完整个文本串。代码实现如下：


int brute_force(string text, string pattern){
  int tlen = text.length();
  int plen = pattern.length();
  for(int i=0; i<=tlen-plen; i++){
    int j = 0;
    for(; j<plen; j++){
      if(text[i+j] != pattern[j])
        break;
    }
    if(j == plen)
      return i;
  }
  return -1;
}

虽然暴力匹配的时间复杂度是O(mn)，但对于短文本串和简单的模式串还是比较适用的。

二、KMP算法

KMP算法是一种效率更高的字符串匹配算法，其核心思想是利用已经匹配的信息避免不必要的字符比较。具体实现可以参考以下代码：


vector<int> prefix_table(string pattern){
  int n = pattern.length();
  vector<int> next(n+1);
  next[0] = -1;
  int j = -1;
  for(int i=1; i<n; i++){
    while(j >= 0 && pattern[j+1] != pattern[i])
      j = next[j];
    if(pattern[j+1] == pattern[i])
      j++;
    next[i] = j;
  }
  return next;
}
int kmp(string text, string pattern){
  vector<int> next = prefix_table(pattern);
  int j = -1;
  for(int i=0; i<text.length(); i++){
    while(j >= 0 && pattern[j+1] != text[i])
      j = next[j];
    if(pattern[j+1] == text[i])
      j++;
    if(j == pattern.length()-1)
      return i-j;
  }
  return -1;
}

该算法的时间复杂度是O(m+n)，其中m和n分别是模式串和文本串的长度。虽然KMP算法在工业界广泛应用，但其实现相对暴力匹配还是比较复杂的。

三、Boyer-Moore算法

Boyer-Moore算法和KMP算法一样，都是一种高效的字符串匹配算法。它在实现上比KMP算法更简单，性能也更好。Boyer-Moore算法的核心思想是尽可能多地跳过不匹配的字符。具体实现可参考以下代码：


int boyer_moore(string text, string pattern){
  int n = text.length();
  int m = pattern.length();
  int i = m-1, j = m-1;
  while(i < n && j >= 0){
    if(text[i] == pattern[j])
      i--;
      j--;
     else {
      int pos = j - bad_char(pattern[j], pattern);
      i += m - min(j, pos+1);
      j = m - 1;
    }
  }
  if(j < 0)
    return i+1;
  else
    return -1;
}
int bad_char(char c, string pattern){
  for(int i=pattern.length()-1; i>=0; i--){
    if(pattern[i] == c)
      return i;
  }
  return -1;
}

Boyer-Moore算法的时间复杂度最小可以达到O(n/m)，最坏情况下仍是O(mn)。但该算法在实战中表现良好，而且相对于KMP算法实现复杂度更低。

总结：以上是C++字符串匹配技巧的三个主要算法，它们各有优缺点，在实际编程中应根据需求选择适合的算法。同时注意算法的实现细节，以保证程序正确性和性能。

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

下一篇: 如何在C++中控制输出的有效位数？

评论区

()

相似文章