什么是KMP算法

KMP算法是由 D.E.Knuth、J.H.Morris 和 V.R.Pratt 提出的形式匹配算法，简称 KMP 算法。KMP 算法对 BF算法进行了很大改善，提高了匹配效率。

KMP算法和BF算法的详细区别这儿就不多做解说，首要解说怎么完成KMP算法

KMP算法剖析

有一个子串 ababc，咱们需求在主串 xxxxxxxxxxxx 中搜索这个子串中搜索这形式串。用 i 和 j 别离表明当时匹配到主串和子串的哪个方位

字符匹配成功：

当时字符匹配成功时，i 和 j 都 +1，匹配下一个字符

字符匹配失利：

当最终一个字符匹配失利时，那么阐明前面的字符都匹配成功，能够确认主串中前四个字符与子串的前四个字符持平。

假如依照BF算法，那么 i 需求指向 主串的第二个字符，j 指向子串的榜首个字符，然后重新匹配

每次产生匹配失利时 i 都需求往回退

而 KMP 算法 的 i 则不需求变化

为了方便观察，咱们能够在当时字符的左面画一条分界线，分界线左面的字符都是已知的

咱们能够让子串每次往左移动一个字符，看看子串的榜首个字符与主串的第二个字符是否持平

显然它们不持平，那么就没有必要在匹配一次这两个字符。再把子串往右移动一个字符

主串的第三个字符是 a，子串的榜首个字符也是 a，它们两个持平，那么比照子串的下一个字符和主串的下一个字符是否持平，显然也持平。主串下一个字符是不知道的，所以不能再移动子串。此刻 i 指向的是这个不知道的字符，而 j 指向的就是要与这个不知道字符匹配的子串字符，即第三个字符（j 之前的字符现已匹配成功了，不需求在进行匹配）。

所以当 第五个字符匹配失利时，咱们不需求让 i 往回退，让 i 坚持不变，j = 3 即可。

当第四个字符匹配失利时，阐明前面三个字符匹配成功，主串与子串的前三个字符都持平

在第四个字符前画一条分界线，分界线左面的字符已知

子串依次往右移动一个字符，比照子串的榜首个字符与主串的第二个字符是否持平，不持平时继续移动子串，比照主串的下一个字符。比照到主串的第三个字符时，与子串的榜首个字符持平，且下一个字符是不知道的字符，中止移动子串。

此刻 i = 4，j = 2。所以当第三个字符匹配失利时，直接让 j = 2 即可

当第三个字符匹配失利时，阐明前面两个字符匹配成功，主串与子串的前两个字符都持平

同样的在第三个字符前画一条分界线，分界线左面的字符已知

子串往右移动进行比照，a 与 b 不持平，继续移动一个字符

此刻子串来到了 i 这个方位，因为 i 所指向的主串的字符不知道，所以要和子串的榜首个字符进行匹配.此刻 i = 3，j = 1

最终剩下榜首和第二个字符，这两个方位有点特别

不管什么情况下，当榜首个字符匹配失利时，让 j = 0；当第二个字符匹配失利时，让 j = 1；

当第二个字符匹配失利时，主串的第二个字符是不知道的，因为咱们只知道它不等于 b，或许等于其他任何值。所以子串需求往右移动一位，和这个不知道的字符进行匹配

能够考虑一下，不论是什么情况下，只需第二个字符没有匹配上，就能够让 j = 1

当榜首个字符匹配失利时，直接从主串的下一位字符开端匹配。 依据前面的规律，i 需求坚持不变，j 需求等于某个值。为了坚持跟之前的处理逻辑相同，能够先让 j = 0，然后 i 和 j 都 +1

整合以上各个字符匹配过错时对应的 j 的值，能够得到一个 next数组

为了和子串字符的位序坚持一致，不运用 0 这个方位，直接从 1 开端表明

在主串中搜索子串的方位时，当某一个字符匹配过错，能够让 j 等于 next 数组中这个字符所对应的值。这样能够越过一些不必要的匹配

用 next 数组来模仿搜索一下子串

主串：a c a b a d a b a b c

子串：a b a b c

榜首位匹配成功，i 和 j 都 +1

第二位匹配失利，依据 next 数组，让 j = 1

榜首位匹配失利，j 置为 0，i 和 j 都 +1

若匹配成功 i 和 j 都 +1，匹配下一个字符，直到遇到匹配失利的字符

第四个字符配对失利，i 坚持不变，j = 2

第二个字符配对失利，i 不变，j = 1

第二个字符配对失利，i 不变，j = 1

后面的字符都能配对成功，假如 j 大于了子串的长度，阐明主串中能够找到子串

代码完成

界说一个结构体，包含一个存放字符串的字符数组和一个变量记载字符串的长度

typedef struct {
	char ch[255];
	int length;
} SString;

准备主串、子串和一个空的 next 数组

字符串从 1 开端，所以 0 的方位能够用一个特别字符表明这个方位为空

next 数组也是从 1 开端存储，所以长度为 S2.length+1

int main() {
    SString S1 = { "#acabadababc", 11 };
    SString S2 = { "#ababc", 5 };
    int next[S2.length+1];
}

完成 next 数组

void nextArr(SString S1, SString S2, int next[]) {
    //  第 o 位用 -1 表明这个方位不运用
    next[0] = -1;
    //  不管什么情况榜首位都为 0
    next[1] = 0;
    //  不管什么情况第二位都为 1
    next[2] = 1;
    //  i 表明第几个字符匹配失利，循环的次数为子串的长度-3
    for (int i = 3; i <= S2.length; i++) {
        //  x 表明每次产生匹配过错，对主串前面已知的字符与子子串比照时主串开端的方位
        //  y 表明表明子串当时比照到的方位
        //  子串和主串的字符配对成功后，x 和 y 都需求 +1，然后比照下一个字符，若主串下一个字符与子串不持平，则需求让主串开端比照的方位往右移一位，所以需求用 z 来记载主串最初开端比照的方位
        int x = 2, y = 1, z = 2;
        //  循环比照主串已知的字符和子串是否相同。x 超越匹配失利的那个字符时中止循环
        while (x < i) {
            //  假如相同，x 好 y 一起 +1
            if (S1.ch[x] == S2.ch[y]) {
                x++;
                y++;
            //  假如不相同，主串开端比照的方位 +1，让 x 回到这个方位，y 回到子串的榜首位
            } else {
                z++;
                x = z;
                y = 1;
            }
        }
        //  比照结束时 y 的值就是子串下一个要匹配的字符的方位
        next[i] = y;
    }
}

把 next 传入搜索函数，依据数组来判别匹配失利时 j 的值应该为多少

int main() {
    SString S1 = { "#acabadababc", 11 };
    SString S2 = { "#ababc", 5 };
    int next[S2.length+1];
    //  把主串、子串和 next 数组传入 nextArr 函数
    nextArr(S1, S2, next);
    //  把主串、子串和 next 数组传入 search 函数
    int result = search(S1, S2, next);
    printf("result: %d\n", result);
}

完成 search 函数

int search(SString S1, SString S2, int next[]) {
    //  i 和 j 表明主串和子串匹配到了哪个字符
    int i = 1, j = 1;
    //  当 i 大于子串的长度或 j 大于子串的长度结束循环
    while (i <= S1.length && j <= S2.length) {
        //  假如这两个字符持平，则匹配下一个字符。因为当榜首个字符匹配失利时，会让 j = 0，然后 i 和 j 都 +1，所以这儿要处理 j = 0 的情况
        if (j == 0 || S1.ch[i] == S2.ch[j]) {
            i++;
            j++;
        } else {
            //  不持平则直接依据 next 设置 j 的值
            j = next[j];
        }
    }
    //  j 大于子串的长度阐明子串匹配成功，返回子串的方位，也就是子串在主串中榜首个字符的方位
    if (j > S2.length) {
        return i - S2.length;
    } else {
        //  匹配失利则返回 0
        return 0;
    }
}

最终运转代码看一下成果是否正确

测验另一个主串和子串

S1 = { “#eabcbcaeeab”, 11 }; S2 = { “#bcaeea”, 6 };

优化 next 数组

咱们有没有发现在上面的字符串中，第三位字符假如匹配失利，依据 next 数组，j 的值应该为 1，也就是说 j 应该指向子串的榜首个字符。可是子串的榜首个字符和第三个字符持平，都是 a，那么第三个字符匹配失利了，阐明主串中这个不知道的字符肯定不是 a，榜首个字符也肯定会匹配失利。所以咱们能够优化一下 next 数组，假如 S2.ch[j] == S2.ch[next[j]] 的话，能够直接让 j 的值等于榜首个字符 j 的值，这样能够越过这次肯定会失利的比照。

基于 next 优化成 nextval 数组

int main() {
    SString S1 = { "#acabadababc", 11 };
    SString S2 = { "#ababc", 5 };
    int next[S2.length+1];
    nextArr(S1, S2, next);
    int nextval[S2.length+1];
    nextvalArr(S2, next, nextval);
    int result = search(S1, S2, nextval);
    printf("result: %d\n", result);
}

完成 nextval 数组

void nextvalArr(SString S2, int next[], int nextval[]) {
    nextval[0] = -1;
    nextval[1] = 0;
    for (int j = 2; j <= S2.length; j++) {
        if (S2.ch[j] == S2.ch[next[j]]) {
            nextval[j] = nextval[next[j]];
        } else {
            nextval[j] = next[j];
        }
    } 
}

运转优化后的代码，成果也没有问题