21xrx.com
2025-06-13 17:26:26 Friday
登录
文章检索 我的文章 写文章
KMP算法C语言代码：实现高效字符串匹配
2023-10-01 18:40:10 深夜i     28     0
KMP算法 C语言代码 高效 字符串匹配

KMP是一种高效的字符串匹配算法，可以在主字符串中查找模式字符串的出现位置。它的思想是利用已经匹配过的部分信息来避免不必要的比较，从而提高匹配的效率。

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

#include <stdio.h>
#include <string.h>
void calculate_lps(char *pattern, int *lps) {
  int len = 0; // 存储前缀和后缀相等的长度
  lps[0] = 0;
  int i = 1;
 
  while (pattern[i]) {
    if (pattern[i] == pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len != 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
}
 
void kmp_search(char *pattern, char *text) {
  int m = strlen(pattern);
  int n = strlen(text);
  int lps[m];
  calculate_lps(pattern, lps);
 
  int i = 0;
  int j = 0;
  while (i < n) {
    if (pattern[j] == text[i]) {
      j++;
      i++;
    }
 
    if (j == m) {
      printf("Pattern found at index %d\n", i - j);
      j = lps[j - 1];
    } else if (i < n && pattern[j] != text[i]) {
      if (j != 0) {
        j = lps[j - 1];
      } else {
        i = i + 1;
      }
    }
  }
}
 
int main() {
  char text[] = "ABABDABACDABABCABAB";
  char pattern[] = "ABABCABAB";
  kmp_search(pattern, text);
 
  return 0;
}

以上代码实现了一个简单的KMP算法，用于在主字符串中查找模式字符串的出现位置。在代码中，先使用`calculate_lps`函数计算模式字符串的最长前缀和最长后缀的匹配长度，存储在`lps`数组中。然后，使用`kmp_search`函数进行字符串匹配，不断根据已匹配的部分信息调整指针位置，从而实现高效的字符串匹配。

这个KMP算法的C语言代码实现了一个基本的功能，但可以根据需要进行扩展和优化。通过使用KMP算法，可以大大提高字符串匹配的效率，特别是对于较长的主字符串和模式字符串。

  
  

评论区