看数据结构的书，字符串章节提到这个字符串匹配的算法。结果一看，真是比较难理解，不愧是三个人想出来的算法，以三个人的名字命名这个算法KMP。书上讲的也是看不明白，只能上网搜搜比较通俗易懂的回答 。结果大部分都是复制粘贴，提到递归什么的，越看越糊涂，估计作者自己都不明白。后来还是在知乎上看到一个点赞数比较多的，结果一看，讲的不错。知乎不愧是程序员用户比较多的平台，大神就是吊。
自己看了看，想了想，动手抄一遍，运行一下，加深记忆理解。

原文地址： 链接

直接开始废话，也都是抄这位作者的，只是为了自己写一遍

一、问题：定位出一个字符串在另一个字符串中完全匹配的位置。

比如目标字符串：abcabcdee 主字符串：xyzabcabcdeezzz
明显一看，结果就是3。在第3位置的a开始匹配到最后。
如果用朴素方法，直接遍历，两个字符串挨个对比，如果不匹配，目标字符串从头开开始，主字符串回到上次匹配位置的下一个位置。每次不匹配的时候，都需要从头开始。最差情况下，主字符串从头到最后，目标字符串每次都是到最后一个字符不匹配，所以时间复杂度就是O（m*n）。

二、朴素方法的弊端

朴素方法每次匹配失败的时候都要从头开始，比如匹配到第6个字符失败了，如果知道了失败了的位置之前到字符串，也就是前5个字符的前缀和后缀的交集，就可以从这个交集长度的位置开始下次匹配了，这样，目标字符串不用从0开始，主字符串也不用回溯到上一次开始的地方了。就节省了很多步。

三、字符串前缀和后缀的交集

前缀：一个字符串的子字符串，确保包含第一个字符，但不包含自身。
后缀：一个字符串的子字符串，确保包含最后一个字符，但不包含自身。
比如：abab
前缀集合：a、ab、aba。后缀集合：b、ab、bab。
所以集合的交集是ab。交集可能不止一个。需要的是最大长度。
有了前后缀交集的长度，说明可以重叠着么长，既然都重叠了，说明前面重叠部分不需要对比了，直接从重叠的下一个位置开始就行了。

KMP的关键就是求目标字符串每个位置的前后缀交集里最大长度。

四、部分匹配表

比如：字符串“abababca”

匹配数组.jpg

首先，对于这个数组，最后一个位置的值是用不上的。因为这个表的用处是在匹配失败的时候需要回溯，回溯位置是前面子字符串的表值+1。
比如目标这个字符串长度是8，匹配到位置6失败了，这时候需要回溯到前5个子字符串，第5位置的值是2，这时候需要回溯到3。从3位置的字符开始接着匹配。
妈的，乱七八糟，说不清。
所以真正用到的值是当前位置前一个位置的表值，最有一个位置的值只能在全部匹配完的时候才用到，但是全部匹配完意味着匹配成功，找到结果了，更用不上它了。所以最后一个值没什么卵用。
而且为了编程方便，就把每个位置对应的值往后推了一格，把最后一个扔了，反正也用不上，第一个空了出来，用-1代替。所以一般叫next数组。匹配失败的时候，回溯位置也不用上一个位置的值+1了，直接就是自己位置对应的值了。

void getNext(char *p, int *arr) {
    
    int i = 0;
    int j = -1;
    arr[0] = -1;
    
    while (i < strlen(p)-1) {
        if (j == -1 || p[i] == p[j]) {
            I++;
            j++;
            arr[i] = j;
        }else{
            j = arr[j];
        }
    }
}

跟着流程走一下，可以发现，这个匹配表的前两位固定是-1、0

寻找过程.jpg

i的位置表示自己的后缀字符串，j表示前缀字符串。
这里比较绕，说不清，真鸡儿难。该睡觉了。

KMP

int kmpMethod(char *str, char *target, int *next) {
    
    int i = 0;
    int j = 0;
    
    while (i < strlen(str) && j < (int)strlen(target)) {
        if (j == -1 || str[i] == target[j]) {
            I++;
            j++;
        }else{
            j = next[j];
        }
    }
    
    if (j == strlen(target)) {
        return i - j;
    }
    
    return -1;
}

匹配成功，各自往后走，各个位置+1。
如果匹配失败，就找当前位置的前面子字符串的匹配表的值，意味找最大重合部分，如果有重合部分，就不用比较前面的了，直接从重合部分开始比较后面的。如果当前位置前面子字符串值是0，意味着没有重合部分，就缩小范围，寻找上一个子字符串的前后缀重合部分，有的话就开始匹配，没有的话，就接着寻找上上一个，直到值是-1，意味着当前位置前面的子字符串没有一个完全没有重叠的部分，就只能从头开始，就各自+1，目标字符串从头开始了，回溯到0，主字符串是一直往后走的，不回溯。
注：strlen得到无符号整型，j的值是-1的时候，会出现-1>无符号数值的问题，所以需要用int强转一下。

说不明白，哈哈。总的来说KMP算法过程容易理解，求部分匹配表那个算法比较难理解。反正这阵子睡眠不好，刚好记录一下。想看的时候直接来简书看，方便。