21xrx.com
2025-06-08 01:45:44 Sunday
文章检索 我的文章 写文章
KMP算法：C语言实现
2023-11-19 06:23:12 深夜i     18     0
KMP算法 字符串匹配 前缀函数 模式串 文本串

KMP算法是一种字符串匹配算法，被广泛应用于文本搜索和模式匹配。它的核心思想是通过预处理目标串和模式串，以避免不必要的回溯，提高匹配效率。在本文中，我们将使用C语言实现KMP算法，并介绍其基本原理和实现步骤。

首先，让我们简要了解KMP算法的基本原理。在传统的字符串匹配算法中，每次匹配失败时，都需要回溯到目标串中的下一个位置，再次进行匹配。而KMP算法则通过利用模式串中的重复子串来实现跳过匹配的过程，从而减少回溯的次数。具体来说，KMP算法通过构建一个辅助数组next[]，用于保存模式串中每个字符之前的最长前缀和最长后缀的匹配长度。当遇到不匹配的字符时，我们可以根据next[]数组中的值确定下一次匹配的位置，避免无效的匹配。

接下来，让我们详细介绍KMP算法的实现步骤。首先，我们需要预处理模式串，计算得到next[]数组。具体步骤如下：

1. 初始化next[0]为-1，next[1]为0。

2. 从第二个字符开始，依次计算next[i]的值：

  a. 如果模式串中第i个字符与前面的字符匹配，则next[i]等于前一个字符的next值加1；

  b. 如果不匹配，则需要考虑当前字符之前的最长前缀和最长后缀的匹配长度，即回溯到前一个字符的next值所对应的位置，继续匹配；

  c. 如果回溯到的位置仍然不匹配，则继续回溯，直到回溯到第一个字符或者找到匹配的位置。

有了next[]数组后，我们可以开始实现KMP算法的匹配过程。具体步骤如下：

1. 初始化目标串和模式串的下标为0。

2. 依次比较目标串和模式串中的字符：

  a. 如果字符匹配，则继续比较下一个字符；

  b. 如果字符不匹配，则根据next[]数组的值更新模式串的下标，跳过不必要的匹配。

3. 如果匹配成功，则返回匹配的位置；否则，返回匹配失败。

下面是一个简单的示例，展示了如何使用C语言实现KMP算法：

#include <stdio.h>
#include <string.h>
void getNext(char *pattern, int *next) {
  int len = strlen(pattern);
  int i = 0, j = -1;
  next[0] = -1;
  while (i < len - 1) {
    if (j == -1 || pattern[i] == pattern[j]) {
      i++;
      j++;
      next[i] = j;
    } else {
      j = next[j];
    }
  }
}
int kmpSearch(char *target, char *pattern) {
  int n = strlen(target);
  int m = strlen(pattern);
  int *next = (int *)malloc(sizeof(int) * m);
  getNext(pattern, next);
  int i = 0, j = 0;
  while (i < n && j < m) {
    if (j == -1 || target[i] == pattern[j]) {
      i++;
      j++;
    } else {
      j = next[j];
    }
  }
  free(next);
  if (j == m)
    return i - j;
   else
    return -1;
  
}
int main() {
  char target[] = "ABABABABCABABABAABABABCABAA";
  char pattern[] = "ABABCABAA";
  int result = kmpSearch(target, pattern);
  if (result != -1) {
    printf("Pattern found at position: %d\n", result);
  } else {
    printf("Pattern not found.\n");
  }
  return 0;
}

在上述代码中，我们首先定义了getNext()函数和kmpSearch()函数，分别用于计算next[]数组和执行KMP算法的匹配过程。在main()函数中，我们给出了一个示例输入，并输出了匹配的位置或者匹配失败的信息。

总结起来，KMP算法是一种高效的字符串匹配算法，可以在文本搜索和模式匹配中发挥重要作用。通过预处理模式串，KMP算法可以避免不必要的回溯，提高匹配效率。在C语言中实现KMP算法时，我们需要借助next[]数组来优化匹配过程。希望本文的介绍能够帮助读者更好地理解和应用KMP算法。

  
  

评论区