C语言实现字符串匹配KMP算法

什么是KMP算法

字符串匹配是计算机科学中的一个基本问题，给定两个文本串A和B，其中A称为主串，B称为模式串，现在要查找B在A中第一次出现的位置，这就是字符串匹配的问题。

KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，它利用了字符串的局部匹配特性来提升匹配效率。与暴力匹配算法相比，KMP算法的时间复杂度为O(n+m)，其中n是主串的长度，m是模式串的长度，相比之下，暴力匹配算法的时间复杂度为O(n*m)。

KMP算法的实现过程

KMP算法实现的核心是构造模式串的next数组，next数组中存储的是模式串中所有前缀子串中最长的相等前缀后缀的长度。

具体实现过程如下：

1. 构造next数组

首先需要预处理模式串的next数组，如果next[i] = j，则表示模式串的前i个字符中，最长的相等前缀后缀的长度为j。

构造next数组的过程分为三步：

（1）初始化next数组为0

（2）通过遍历模式串生成next数组，找到当前位置前面最长相等前后缀的长度

（3）当找到当前位置的最长相等前后缀时，更新next数组

1. 匹配主串和模式串

利用已经构造好的next数组，进行主串和模式串的匹配

如果模式串和主串的字符匹配成功，模式串和主串的索引值都加1；如果匹配不成功，则主串的索引值不变，模式串的索引值变为next[j]。

最后如果匹配成功，返回主串中匹配的起始位置，如果匹配失败，返回-1。

KMP算法的C语言实现

以下是KMP算法在C语言中的实现，包含匹配函数和构造next数组的函数：

#include <stdio.h>
#include <string.h>

void getNext(char *pattern, int *next) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < strlen(pattern)) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int kmp(char *text, char *pattern) {
    int i = 0, j = 0;
    int next[strlen(pattern)];
    getNext(pattern, next);
    while (i < strlen(text) && j < strlen(pattern)) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == strlen(pattern)) {
        return i - j;
    } else {
        return -1;
    }
}

示例

以下是对上述KMP算法的两条示例说明。

示例1

假设我们要在文本串中查找模式串ABCDABD，文本串为ABCDEFGABCDABCEFG，上述kmp函数的调用过程如下：

kmp("ABCDEFGABCDABCEFG", "ABCDABD");

得到的结果是：

7

表示模式串ABCDABD在文本串中从第7个位置开始出现。

示例2

假设我们要在文本串中查找模式串hello，文本串为hello world，上述kmp函数的调用过程如下：

kmp("hello world", "hello");

得到的结果是：

0

表示模式串hello在文本串中从第0个位置开始出现。

总结

KMP算法是一种高效的字符串匹配算法，在实现过程中需要理解next数组的概念和构造方法，代码实现过程相对较简单，但需要考虑到细节问题，如边界处理，数组下标从0开始等。