先看代碼

#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;
}

//獲取一個(gè)匹配字符串的部分匹配表
int* kmpNext(char* myStr){
    //創(chuàng)建一個(gè)數(shù)組保存部分匹配值
    int* arr = (int*)malloc(sizeof(int)* strlen(myStr));
    arr[0]=0;  //如果字符串長(zhǎng)度是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;
}

代碼解讀

歸根結(jié)底就是不要走重復(fù)的路

先要根據(jù)目標(biāo)匹配字符串構(gòu)建部分匹配表

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

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

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

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

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

j = arr[j-1]; //發(fā)現(xiàn)不匹配，就需要返回上一次的最長(zhǎng)的公共前后綴的前綴起始位置？？？

可以以AADAAA這個(gè)字符串，來進(jìn)行理解。就是當(dāng)D和A不相等的時(shí)候，讓最長(zhǎng)公共前綴退后一位，再去比較。這個(gè)時(shí)候AA和AA又成為了前后綴的公共前綴。