先看代碼

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

/**
 *
 * @param srcStr
 * @param descStr
 * @param arr 部分匹配表
 * @return
 */
int kmpSearch(char* srcStr,char* descStr,int* arr){
    for (int i = 0,j=0; i < strlen(srcStr); ++i) {

        while (j>0 && srcStr[i] != descStr[j]){
            j=arr[j-1];
        }

        if(srcStr[i] == descStr[j]){
            j++;
        }

        if(j== strlen(descStr)){
            return i-j+1;
        }
    }
    return -1;
}

//獲取一個匹配字符串的部分匹配表
int* kmpNext(char* myStr){
    //創建一個數組保存部分匹配值
    int* arr = (int*)malloc(sizeof(int)* strlen(myStr));
    arr[0]=0;  //如果字符串長度是1，部分匹配值就是0

    for (int i = 1,j=0; i < strlen(myStr) ; ++i) {
        while (j>0 && myStr[i]!= myStr[j]){
            j = arr[j-1];
        }

        if(myStr[i] == myStr[j]){
            j++;
        }

        arr[i]=j;
    }

    return arr;
}

int main() {

    char* srcStr = "hello world";
    char* descStr = "wo";
    int* arr = kmpNext(descStr);
    int index = kmpSearch(srcStr,descStr,arr);
    printf("%d",index);
    return 0;
}

代碼解讀

歸根結底就是不要走重復的路

先要根據目標匹配字符串構建部分匹配表

先看部分匹配表的核心代碼

 int* arr = (int*)malloc(sizeof(int)* strlen(myStr));
    arr[0]=0;  //如果字符串長度是1，部分匹配值就是0

    for (int i = 1,j=0; i < strlen(myStr) ; ++i) {
        while (j>0 && myStr[i]!= myStr[j]){
            j = arr[j-1]; //發現不匹配，就需要返回上一次的最長的公共前后綴的前綴起始位置？？？
        }
        if(myStr[i] == myStr[j]){
            j++;
        }
        arr[i]=j;
    }

解讀：當目標字符串就一個字符的時候，部分匹配表就是0，沒啥說的。當目標字符串長度超過1的時候，讓j=0，i=1，這樣就不斷的比較不斷加長的前后綴。（尋找最長就行）
例如：j=0,i=1;就是AB，兩個字符不相等；arr[1]=0;-----------,類推
j=0,i=4;就是ABCDA，此時兩個字符相等，arr[4]=1,注意此時j=1；
j=1,i=5,就是ABCDAB,此時第二個字符也相等，也就是前后綴有共同的AB長度的子串，arr[i]=2,j=2;
j=2,i=6,就是ABCDABD，此時第三個字符不相等，此時執行while邏輯，j=2>0; j=arr[2-1]=0;
最后就構成了arr[]={0,0,0,0,1,2,0};的部分匹配表。

其中最難理解是這行代碼：

j = arr[j-1]; //發現不匹配，就需要返回上一次的最長的公共前后綴的前綴起始位置？？？

可以以AADAAA這個字符串，來進行理解。就是當D和A不相等的時候，讓最長公共前綴退后一位，再去比較。這個時候AA和AA又成為了前后綴的公共前綴。