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

KMP算法C语言实现

2023-10-02 12:27:06 深夜i -- --

KMP算法 C语言实现字符串匹配前缀函数

KMP算法是一种高效的字符串匹配算法，它的实现主要基于对字符串的模式匹配过程中出现不匹配时的重定位。本文将介绍如何使用C语言实现KMP算法。

首先，我们需要了解KMP算法的基本原理。它的核心思想是利用已经匹配过的子串的信息来避免不必要的比较。当出现不匹配时，根据已经匹配的子串的前缀和后缀的最大公共部分，将模式串移动到对应位置，然后继续比较。

接下来，我们可以开始编写KMP算法的C语言实现。首先，我们需要创建一个辅助函数，该函数用于计算模式串的前缀表。前缀表是一个数组，其中每个元素表示当前位置之前的子串的最长相同前缀和后缀的长度。我们可以按照以下方式实现该函数：


void computePrefixTable(char *pattern, int *prefixTable) {
  int length = strlen(pattern);
  int len = 0;
  prefixTable[0] = 0;
  int i = 1;
  
  while (i < length) {
    if (pattern[i] == pattern[len]) {
      len++;
      prefixTable[i] = len;
      i++;
    }
    else {
      if (len != 0) {
        len = prefixTable[len - 1];
      }
      else {
        prefixTable[i] = 0;
        i++;
      }
    }
  }
}

接下来，我们可以使用上述辅助函数来实现KMP算法本身。在该函数中，我们会遍历文本串和模式串，并且在匹配失败时，根据前缀表的信息进行重定位。


void kmpSearch(char *text, char *pattern) {
  int textLength = strlen(text);
  int patternLength = strlen(pattern);
  
  int *prefixTable = (int*)malloc(sizeof(int) * patternLength);
  computePrefixTable(pattern, prefixTable);
  
  int i = 0;
  int j = 0;
  
  while (i < textLength) {
    if (text[i] == pattern[j]) {
      i++;
      j++;
    }
    
    if (j == patternLength) {
      printf("Pattern found at index %d\n", i - j);
      j = prefixTable[j - 1];
    }
    
    else if (i < textLength && text[i] != pattern[j]) {
      if (j != 0) {
        j = prefixTable[j - 1];
      }
      else {
        i++;
      }
    }
  }
  
  free(prefixTable);
}

最后，我们可以在main函数中调用kmpSearch函数，以实现对文本串的模式匹配。


int main() {
  char *text = "ABABDABACDABABCABAB";
  char *pattern = "ABABCABAB";
  
  kmpSearch(text, pattern);
  
  return 0;
}

以上就是KMP算法的C语言实现。通过该算法，我们可以高效地在字符串中进行模式匹配，提高了搜索效率。在实际应用中，KMP算法被广泛应用于字符串匹配、文本搜索等领域。希望本文对你理解和应用KMP算法有所帮助。

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

下一篇: iOS上使用FFmpeg开发

评论区

()

相似文章