浅谈 KMP 算法

最近在复习数据结构，学到了 KMP 算法这一章，似乎又迷糊了，记得第一次学习这个算法时，老师在课堂上讲得唾沫横飞，十分有激情，而我们在下面听得一脸懵比，啥？这是个啥算法？啥玩意？再去看看书，完全听不懂呀？总之，觉得十分懵比，课后去看了一些视频和博客，才慢慢有一点理解，学习不是一蹴而就的，需要脚踏实地的努力。过了三年，重新温习这个算法，似乎依旧不是很明白，理解得不够透彻，重新拾起课本和视频，认真学习这个算法。

１.KMP 算法简介

KMP 算法是由三位老前辈（D.E.Knuth，J.H.Morris 和 V.R.Pratt )的研究结果，该算法巧妙之处在于避免重复遍历的情况，全称叫做克努特-莫里斯-普拉特算法，简称 KMP 算法，D.E.Knuth，编写了《计算机程序设计艺术》写完了第四卷，这部著作被誉为计算机领域中的“相对论”。

2.子串 next 数组的计算

KMP 算法关键点是先求出 next[] 数组，这个 next 数组只与模式匹配串有关，例如以 "abababca" 这个子串计算一下它的 next 数组

下标为 index = 0 开始 ,

index = 0 ，"a" 的前缀和后缀都为空集，value = 0；

index = 1，"ab" 的前缀和后缀分别为 "a" 和 "b"，不相等，value = 0；

index = 2， "aba" 的前缀是 "a"、 "ab"，后缀是 "ba"、"a"，有相同交集 "a"，长度为 1, value = 1；

index = 3， "abab" 的前缀是 "a"、"ab"、"aba"，后缀是 "bab"、"ab"、"b"，有最长相同交集 "ab"，长度为 2，value = 2；

index = 4，"ababa" 的前缀是 "a"、"ab"、"aba"、"abab"，后缀是 "baba"、"aba"、"ba"、"a"，有最大相同交集 "aba"，长度为 3， value = 3；

index = 5，"ababab" 的前缀是 "a"、"ab"、"aba"、"abab"、"ababa"，后缀是 "babab"、"abab"、"bab"、"ab"、"b"，有最长相同交集 "abab"，长度为 4， value = 4；

index = 6，"abababc" 的前缀是 "a"、"ab"、"aba"、"abab"、"ababa"、"ababab"，后缀是 "bababc"、"ababc"、"babc"、"abc"、"bc"、"c"，没有相同交集，value = 0；

index = 7，"abababca" 的前缀是 "a"、"ab"、"aba"、"abab"、"ababa"、"abababc"，后缀是 "bababca"、"ababca"、"babca"、"abca"、"bca"、"ca"、"a"，有相同交集 "a"，长度为1，value = 1；

最后结果如下：

char: | a | b | a | b | a | b | c | a |

index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

3、如何使用 next[] 数组

得到子串的 next 数组以后，在目标串中匹配使用 next 数组，通过使用 next 数组避免重复的匹配已经匹配过的元素，如果找到长度为 partial_match_length 的部分匹配，并且表 next [partial_match_length]> 1，我们可以提前跳过 partial_match_length - next[partial_match_length-1] 个字符

总结移动位数 = 已匹配的字符数 - 对应的部分匹配值

char: | a | b | a | b | a | b | c | a |

index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

以 "bacbababaabcbab" 为例说明它的匹配过程，第一次匹配，调到 index = 1 位置，如下

bacbababaabcbab

abababca

不难看出，部分匹配的长度为 partial_match_length = 1，但是在 next [ partial_match_length - 1] = 0，也就是 next[0] = 0，这个元素，所以我们不需要跳过任何元素，接下来 cb 和 a 都不匹配直接向右匹配，到了下一个 a 匹配的地方

bacbababaabcbab

| | | | |

　 abababca

来到这个地方，你会发现此时部分匹配的长度为 5 ， partial_match_length = 5， next[partial_match_length - 1] = next[4]，查 next 数组，next[4] = 3，这就意味着在接下来的匹配中我们要跳过 partial_match_length - next[partial_match_length-1] ，即 5 - next[4] = 5 - 3 = 2，要跳过 2 个字符，所以接下来的匹配应该变成了如下所示：

bacbababaabcbab

xx | | |

　 abababca

xx 表示跳过了，部分匹配长度为 3， partial_match_length = 3，next[partial_match_length - 1] = next[2] = 1，接下来匹配中要跳过

partial_match_length - next[partial_match_length - 1]，即 3 - 1 = 2，跳过 2 个字符后的匹配情况如下：

bacbababaabcbab

xx |

　 abababca

得到部分匹配长度为 1 ， partial_match_length = 1， next[partial_match_length - 1] = 0，接下来匹配不用跳过字符，向右匹配，匹配串比剩余的主串要长，所以没有找到匹配的字符串。

4、KMP 算法代码实现，使用 C 语言实现

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

void get_next(char T[],int next[])//next数组

{

    int i,j;

    i=;//前

    j=;//后

    next[]=;

    while(j<T[]) {

        if(i== || T[i]==T[j])

        {

            i++;

            j++;

            next[j]=i;

            /*if(T[i]!=T[j])

            {

                next[j]=i;

            }

            else

            {

                next[j]=next[i];

            }*/

        }

        else

        {

            i=next[i];

        }

    }

}

int Index_KMP(char S[],char T[])

{

    int next[];

    int i=;

    int j=;

    get_next(T,next);//获得next数组

    /*

    for(i=1;i<=T[0];i++)

    {

            printf("%d ",next[i]);

    }

    */

    while(i<=S[] && j<=T[])

    {

        if(j==||S[i]==T[j])

        {

           i++;

           j++;

        }

        else

        {

            j=next[j];

        }

    }

    if(j>T[])

        return i-T[];

    return ;

}

int main (){

    char T[],S[];

    int i,k;

    while(scanf("%s %s",S,T)!=EOF)

    {

        k=strlen(T);

        for(i=strlen(T);i>;i--)//向后移动

        {

            T[i]=T[i-];

        }

        T[]=k;

        k=strlen(S);

        for(i=strlen(S);i>;i--)//向后移动

        {

            S[i]=S[i-];

        }

        S[]=k;

        printf("%d\n",Index_KMP(S,T));

    }

    return ;

}

运行结果如下：

4 为第一个出现匹配字符串的数字下标从 1 开始

5、个人总结

经过这次对于 KMP 算法的练习，使我重新练习了一遍，关于 KMP 中算法实现的某些步骤依旧不是很清楚，有些地方想得还不是特别明白，也许这就是差距。今天出现了一些代码的 Bug，为了解决 Bug 查了一些网站的资料，重新温习了 C语言的使用，今天过得很充实。

更多有趣、好玩、实用的内容，请关注我的微信公众号：

参考资料：

http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

https://liam.page/2016/12/20/KMP-Algorithm/

https://blog.dotcpp.com/a/8986

巴特西

浅谈 KMP 算法

最新文章

热门文章