KMP算法C语言代码-实现高效字符串匹配 |21xrx.com

KMP算法C语言代码-实现高效字符串匹配

2023-07-27 13:32:27 深夜i -- --

KMP算法 C语言代码高效字符串匹配

KMP算法是一种高效的字符串匹配算法，它的思想是通过预处理匹配串，获得一个辅助数组，利用这个数组来指导匹配过程中的回溯，从而达到提高匹配效率的目的。以下是KMP算法的C语言实现代码：


#include <stdio.h>
#include <string.h>
void getLPS(char *pattern, int *lps) {
  int len = 0;
  int i = 1;
  lps[0] = 0;
  while (pattern[i] != '\0') {
    if (pattern[i] == pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
}
void KMP(char *text, char *pattern) {
  int n = strlen(text);
  int m = strlen(pattern);
  int lps[m];
  getLPS(pattern, lps);
  int i = 0;
  int j = 0;
  while (i < n) {
    if (pattern[j] == text[i]) {
      j++;
      i++;
    }
    if (j == m) {
      printf("匹配成功，位置: %d\n", i - j);
      j = lps[j - 1];
    } else if (i < n && pattern[j] != text[i]) {
      if (j) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
}
int main() {
  char text[] = "ABABDABACDABABCABAB";
  char pattern[] = "ABABCABAB";
  KMP(text, pattern);
  return 0;
}

KMP算法的核心在于构建最长公共前后缀数组lps，通过预处理模式串（即匹配串），找出每个位置上最长可匹配前缀的长度。在匹配过程中，当遇到不匹配的字符时，利用lps数组跳过已经匹配过的字符，避免不必要的比较。

以上代码中，先调用getLPS函数得到lps数组，然后在KMP函数中利用lps数组进行匹配。当匹配成功时，输出匹配的起始位置，然后根据lps数组跳过已匹配的部分，继续匹配过程，直到遍历完所有字符。

通过KMP算法，可以在匹配时间复杂度为O(n+m)的情况下实现高效的字符串匹配。

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

下一篇: Python中OpenCV imwrite函数的用法

评论区

()

相似文章