使用C语言实现KMP算法 |21xrx.com

使用C语言实现KMP算法

2023-07-27 14:31:02 深夜i -- --

C语言 KMP算法实现

KMP算法，即Knuth-Morris-Pratt算法，是一种用于字符串匹配的快速算法。它利用了字符串的局部信息，避免了不必要的比较操作，从而提高了字符串匹配的效率。本文将介绍如何使用C语言实现KMP算法。

首先，KMP算法的核心思想是利用一个部分匹配表（Partial Match Table，简称PMT），该表记录了模式串中每个字符在遇到不匹配时应该回退的位置。实现KMP算法的关键步骤包括构建部分匹配表和进行字符串匹配。

下面是实现KMP算法的示例代码：


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void buildPMT(char *pattern, int *PMT) {
  int len = strlen(pattern);
  PMT[0] = 0;
  int i = 1, j = 0;
  while (i < len) {
    if (pattern[i] == pattern[j]) {
      j++;
      PMT[i] = j;
      i++;
    }
    else {
      if (j != 0) {
        j = PMT[j - 1];
      }
      else {
        PMT[i] = 0;
        i++;
      }
    }
  }
}
void KMP(char *text, char *pattern) {
  int textLen = strlen(text);
  int patternLen = strlen(pattern);
  int *PMT = malloc(sizeof(int) * patternLen);
  buildPMT(pattern, PMT);
  int i = 0, j = 0;
  while (i < textLen) {
    if (text[i] == pattern[j]) {
      i++;
      j++;
    }
    if (j == patternLen) {
      printf("Pattern found at index: %d\n", i - j);
      j = PMT[j - 1];
    }
    else if (i < textLen && text[i] != pattern[j]) {
      if (j != 0) {
        j = PMT[j - 1];
      }
      else {
        i++;
      }
    }
  }
  free(PMT);
}
int main() {
  char text[] = "ABABDABACDABABCABAB";
  char pattern[] = "ABABCABAB";
  KMP(text, pattern);
  return 0;
}

在这段代码中，我们首先定义了两个函数，`buildPMT`用于构建部分匹配表，`KMP`用于进行字符串匹配。然后，我们在`main`函数中定义了一个测试用例，并调用KMP函数进行字符串匹配。运行程序后，将会输出模式串在文本中的匹配位置。

以上就是使用C语言实现KMP算法的代码和相关解释。通过这段代码，我们可以看到KMP算法的简洁且高效的实现方式。希望通过本文的介绍，读者能够更好地理解和应用KMP算法。

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

下一篇: FFmpeg 实现输入源的切换功能

评论区

()

相似文章