[C++知识库]字符串匹配算法之KMP算法（C语言实现）

#1、KMP算法：

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

##2、代码

#include<string.h>
#include<malloc.h>
#include<assert.h>
#include<string.h>
#include<stdio.h>
    /*
    * str代表主串
    * sub代表字串
    * pos代表从主串的pos位置开始找
    */
void GetNext(char* sub, int* next, int lenSub)
    {
        next[0] = -1;
        next[1] = 0;
        int i = 2;//当前i下标
        int k = 0;//前一项的k
        while(i < lenSub)
            {
            if (k == -1 || sub[i - 1] == sub[k]) {
                next[i] = k + 1;
                i++;
                k++;
           
        }
            else {
                k = next[k];
           
        }
            }
    }
int KMP(char* str, char* sub, int pos)
    {
        assert(str != NULL && sub != NULL);
        int lenStr = strlen(str);
        int lenSub = strlen(sub);
        if (lenStr == 0 || lenSub == 0)
            return -1;
        if (pos < 0 || pos >= lenStr)
                return -1;
    
        int* next = (int*)malloc(sizeof(int) * lenSub);
        assert(next != NULL);
        GetNext(sub, next, lenSub);
   
        int i = pos;//遍历主串
        int j = 0;//遍历字串
        while (i < lenStr && j < lenSub)
            {
                if (j == -1 || str[i] == sub[j]) {
                    i++;
                    j++;
             
            }
            else {
                    j = next[j];
             
            }
            }
        if (j >= lenSub)
                return i - j;
            return -1;
       
           
    }
int main()
{
        printf("%d\n", KMP("ddeabcd", "ff", 0));
        return 0;
}