KMP算法原理和实现-C语言实现

简介

什么是KMP算法？百度百科

KMP 算法是一种改进的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人们称它为克努特 — 莫里斯 — 普拉特操作（简称 KMP 算法）。KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next () 函数实现，函数本身包含了模式串的局部匹配信息。KMP 算法的时间复杂度相对于暴力搜索的时间复杂度O（m*n）而言，是O（m+n）。

也就是在字符串text中寻找一个子字符串pattern，看这个子字符串是否存在于主串中，例如text='abc'和 pattern1='ab'以及 pattern2='ca' ，pattern1在主串中，而pattern2不在主串中，可以返回出现位置的索引。

字符串匹配暴力法

LC28 找出字符串中第一个匹配项的下标，以下是暴力搜索的代码

int strStr(char * haystack, char * needle){
    int len1 = strlen(haystack), len2 = strlen(needle);
    for (int i = 0; i <= len1 - len2; i++) }
        if (haystack[i] == needle[0]) {
            int j = 1;
            for (; j < len2; j++) {
                if (haystack[i+j] != needle[j]) break;
            }
            if (j == len2) return i;
        }
    }
    return -1;
}

KMP算法原理

上面的暴力搜索算法，在遇到Text="aaa.....aaaa"和Pattern="aa.....b"这种情况下会获得最大的时间复杂度m*n，原因在于i在主串中每次匹配失败的时候需要回溯。KMP算法提供了一个主串i不用回溯的方法，即在发现字符串不匹配的时候，利用之前匹配的子串，将pattern子串移动到某个位置，这样主串中i的位置就不用回溯，复杂度相应的就降到了O（m+n）。

如图中所示，当i=j=3的时候Text[i]!=Pattern[j]，这时候前面三个字符子串“aba”是重复的。假设有两个字符串“aba”，其中一个字符串进行滑动操作，一格一格的滑动，直到找到两个字符串的重叠部分是相等的。图中的左下部分即“aba”的滑动得到的重复字符串即“a”，重叠长度是1。这里就很好理解网络上很多关于KMP原理讲解提到的前缀子串、后缀子串和前后缀子串最大重叠长度的概念了。

需要特别注意两个点：

所有提到的前缀、后缀子串、公共长度都是针对"aba"这个Text和PPattern匹配过程中在遇到字符不匹配的时候，前述匹配的字符，这里的示例是"aba"，也有可能是"a"，"ab"，"aba"，"abab"， "ababc"。是上述这些字符子串进行滑动能找到的最大的重叠长度决定了j的重定位，这些子串的滑动最大重叠长度就是next数组。
在j重新定位后需要进行的操作，Text[i]和Patter[j]相等与否会有不同的操作。

next数组

上面提到的Text和Pattern的前述匹配字符即Pattern的所有子串[a,ab,aba,abab,ababa]，这些子串在滑动过程中得到最大的重叠长度就是j新定位的值，即[0,0,1,2,0]。下面是针对"abab"、"ababa"子串滑动过程中得到最大重叠长度的演示，j就定位在最大重复长度的后一位，因为数组的下标是0开始的，j的新定位刚好是最大重叠的长度值。

j重新定位后操作

Text[i]和Pattern[j]相等，i和j同时移动。
Text[i]和Pattern[j]不相等，移动j，移动j的方法即j=next[j-1]，这样能保持Text和Pattern字符串在j之前的重叠部分依旧一样（这里的理解是关键，就是一直在讲的next数组的作用，j之前的字符子串是重复的！！！！！！！）。
j=next[j-1]，重复上面的判断，进行相应的操作，Text[i]和Pattern[j]相等或者Text[i]和Pattern[j]一直不相等，一直移动j，直到j=0，这时候再移动i。

以上就是KMP算法迭代的核心思路，下面要解决的问题就是next数组的生成。

next数组的生成

next数组的生成原理和上面的滑动匹配的原理也是一样的，如图中所示，还是采用i和j进行滑动，i 是0的时候，next[i] = 0，从i=1和j=0开始进行数组的赋值，分为以下几种判断情况：

str[i] = str[j]的时候，next[i]的值就是j的位置，因为数组下标是0，所以next[i] = j+1。
str[i] != str[j]的时候，需要对j进行回溯找到最大重复长度，回溯的方法上面讲过了用j = next[j-1]，直到str[i] = str[j]， next[i] = j + 1，或者一直回溯到j = 0时候，str[i] != str[j]那么next[i] = 0。

下面是实现next数组生成的代码

#include 
#include 
#include 

int main() {
    char str[100];
    scanf("%s", str);
    int len = strlen(str);
    int *next = calloc(len, sizeof(int));
    int i = 1, j = 0;
    while (i < len) {
        if (str[i] == str[j]) {
            next[i] = j + 1;
            i++;
            j++;
        }
        else {
            if (j > 0) {
                j = next[j-1];
            }
            else {
                next[i] = 0;
                i++;
            }
        }
    }
    for (int i = 0; i < len; i++) {
        printf("%d ", next[i]);
    }
    printf("\n");

    return 0;
}
/*input && output
ababc
0 0 1 2 0
*/

KMP的实现

下面是KMP算法实现的代码

#include 
#include 
#include 

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

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

int main() {
    char text[] = "abaacababcac";
    char pattern[] = "ababc";
    int *next = calloc(strlen(pattern), sizeof(int));
    next_arrary(pattern, next);
    printf("%d\n", strStr(text, pattern, next));
    return 0; 
}

上面的代码只是demo版本，没有检查是否有问题，下面是我写的LC28的题解，经过算例检验的，应该没有问题。

void next_arrary(char *needle, int *next) {
    int len = strlen(needle);
    if (len > 1) {
        int i = 1, j = 0;
        while (i < len) {
            if (needle[i] == needle[j]) {
                next[i] = j + 1;
                j++;
                i++;
            }
            else {
                if (j > 0) {
                    j = next[j-1];
                }
                else {
                    next[i] = 0;
                    i++;
                }
            }
        }
    }
}

int strStr(char * haystack, char * needle){
    int len1 = strlen(haystack), len2 = strlen(needle);
    if (len1 < len2) return -1;
    int *next = calloc(len2, sizeof(int));
    next_arrary(needle, next);
    int i= 0, j = 0;
    while (i < len1) {
        if (haystack[i] == needle[j]) {
            if (j == len2 - 1) return i - len2 + 1;
            i++;
            j++;
        }
        else {
            if (j > 0) {
                j = next[j-1];
            }
            else {
                i++;
            }
        }
    }
    return -1;
}

和暴力搜索相比时间相差还是比较明显的

简介