21xrx.com
2025-02-28 19:42:29 Friday
文章检索 我的文章 写文章
KMP算法C++实现:详解与示例
2023-10-13 15:10:48 深夜i     30     0
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算法。

  
  

评论区