先看代码

#include 
#include 
#include 

/**
 *
 * @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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

代码解读

归根结底就是不要走重复的路

先要根据目标匹配字符串构建部分匹配表

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

 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;
    }
1
2
3
4
5
6
7
8
9
10
11
12

解读：当目标字符串就一个字符的时候，部分匹配表就是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]; //发现不匹配，就需要返回上一次的最长的公共前后缀的前缀起始位置？？？
1

可以以AADAAA这个字符串，来进行理解。就是当D和A不相等的时候，让最长公共前缀退后一位，再去比较。这个时候AA和AA又成为了前后缀的公共前缀。