KMP算法C语言实现：详解与代码示例 |21xrx.com

KMP算法C语言实现：详解与代码示例

2023-09-23 18:32:11 深夜i -- --

KMP算法 C语言实现详解代码示例字符串匹配

KMP算法是一种用于字符串匹配的高效算法，它的优势在于能够根据已经匹配的部分字符来跳过不必要的比较，从而提高算法的效率。本文将介绍KMP算法的原理，并给出一个C语言实现的代码示例。

KMP算法的核心思想是利用已经匹配的部分字符来确定下一次比较的起始位置。具体而言，算法从目标字符串和模式字符串的开头开始比较，如果发现某个字符不匹配，则利用模式字符串的前缀信息来确定下一次比较的位置，而不是从头开始重新比较。

KMP算法的关键在于构建一个部分匹配表，该表记录了模式字符串中每个字符对应的最长前缀后缀匹配长度。部分匹配表的构建是算法的核心操作，可以通过一个循环来完成。

具体的部分匹配表构建算法如下：


void partialMatchTable(const char *pattern, int *table) {
  int n = strlen(pattern);
  for (int i = 0; i < n; i++) {
    int len = table[i - 1];
    while (len > 0 && pattern[i] != pattern[len]) {
      len = table[len - 1];
    }
    if (pattern[i] == pattern[len]) {
      len++;
    }
    table[i] = len;
  }
}

构建完成部分匹配表后，就可以利用它来进行匹配操作。匹配操作的实现如下：


int KMP(const char *text, const char *pattern) {
  int m = strlen(text);
  int n = strlen(pattern);
  int *table = (int *) malloc(sizeof(int) * n);
  partialMatchTable(pattern, table);
  int i = 0; // text索引
  int j = 0; // pattern索引
  while (i < m) {
    if (text[i] == pattern[j]) {
      i++;
      j++;
      if (j == n) { // 匹配成功
        free(table);
        return i - j;
      }
    } else {
      if (j == 0) {
        i++;
      } else {
        j = table[j - 1];
      }
    }
  }
  free(table);
  return -1; // 未找到匹配
}

上面的代码中，变量i和j分别作为text和pattern的索引，用于指示当前比较的位置。如果匹配成功，i和j都向前移动一位；如果匹配失败，根据部分匹配表来更新j的位置。

最后，我们可以通过调用KMP函数来进行字符串的匹配操作，如下所示：


int main() {
  const char *text = "ABABABABA";
  const char *pattern = "ABA";
  int idx = KMP(text, pattern);
  if (idx != -1) {
    printf("匹配成功，位置为：%d\n", idx);
  } else {
    printf("未找到匹配。\n");
  }
  return 0;
}

运行上述代码可以得到如下输出结果：

匹配成功，位置为：0

可见，KMP算法成功地在目标字符串中找到了模式字符串的匹配位置。

总的来说，KMP算法是一种高效的字符串匹配算法，它利用部分匹配表来跳过不必要的比较，从而提高了匹配的效率。通过本文的介绍，读者可以了解KMP算法的原理，并通过C语言实现来加深对该算法的理解。

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

下一篇: 无法打开m4s文件的ffmpeg解决方案

评论区

()

相似文章