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

KMP算法C语言实现

2023-07-28 06:03:13 深夜i -- --

KMP算法 C语言实现字符串匹配前缀表模式匹配

KMP算法是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。它的核心思想是利用已经匹配过的部分字符，尽可能减少不必要的比较次数，从而提高匹配效率。在本文中，我们将使用C语言来实现这个算法。

首先，我们需要定义一个辅助数组next，用于储存模式串中每个位置前面的最长公共前后缀长度。这个长度表示，当模式串的某个字符与主串的某个字符不匹配时，应该将模式串右移的位数。具体的计算方法是通过比较模式串中每个位置的前缀和后缀，找到最长公共前后缀，并存储在next数组中。

接下来，我们需要实现一个函数，用于将模式串在主串中进行匹配。在这个函数中，我们需要使用一个指针i记录主串中当前位置的索引，使用一个指针j记录模式串中当前位置的索引。

具体的算法步骤如下：

1. 初始化指针i和j为0，然后循环比较直到字符串结束。

2. 若当前字符匹配成功，则将i和j都向右移动一位。

3. 若当前字符匹配失败，则根据next数组的值，将指针j右移，同时保持指针i不动。

4. 若指针j移动到模式串的末尾，则匹配成功，返回当前位置。

下面是用C语言实现KMP算法的代码：


#include <stdio.h>
#include <string.h>
// 计算模式串前缀和后缀的最大长度
void calcNext(char *pattern, int *next) {
  int i, j;
  int len = strlen(pattern);
  next[0] = -1;
  j = -1;
  for(i = 1; i < len; i++) {
    while(j >= 0 && pattern[i] != pattern[j + 1]) {
      j = next[j];
    }
    if(pattern[i] == pattern[j + 1]) {
      j++;
    }
    next[i] = j;
  }
}
// KMP算法匹配字符串
int KMP(char *text, char *pattern) {
  int i, j;
  int len1 = strlen(text);
  int len2 = strlen(pattern);
  int next[len2];
  calcNext(pattern, next);
  j = -1;
  for(i = 0; i < len1; i++) {
    while(j >= 0 && text[i] != pattern[j + 1]) {
      j = next[j];
    }
    if(text[i] == pattern[j + 1]) {
      j++;
    }
    if(j == len2 - 1)
      return i - j;
    
  }
  return -1;
}
int main() {
  char text[] = "ABABABABCD";
  char pattern[] = "ABCD";
  int pos = KMP(text, pattern);
  if(pos != -1) {
    printf("Pattern found at index %d\n", pos);
  }
  else {
    printf("Pattern not found\n");
  }
  return 0;
}

以上代码实现了KMP算法的匹配过程，并在主函数中进行测试。我们定义了一个文本字符串text和一个模式串字符串pattern，然后调用KMP函数进行匹配。如果匹配成功，将输出模式串在文本字符串中的起始位置；否则，将输出"Pattern not found"。

通过以上代码，我们成功地实现了KMP算法的字符串匹配过程。这个算法具有较高的效率，适用于各种字符串匹配问题，特别是在长文本和长模式串的匹配中，可以提供快速的结果。希望本文对您理解KMP算法的C语言实现有所帮助。

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

下一篇: 使用FFmpeg选择关键帧进行复制时间戳

评论区

()

相似文章