浅谈 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=0;//前
    j=1;//后
    next[1]=0;
    while(j<T[0]) {
        if(i==0 || 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[1000];
    int i=1;
    int j=1;
    get_next(T,next);//获得next数组
    /*
    for(i=1;i<=T[0];i++)
    {
            printf("%d ",next[i]);
    }
    */
    while(i<=S[0] && j<=T[0])
    {
        if(j==0||S[i]==T[j])
        {
           i++;
           j++;
        }
        else 
        {
            j=next[j];
        }
    }
    if(j>T[0])
        return i-T[0];
    return 0;
 
}
int main (){
    char T[1000],S[1000];
    int i,k;
    while(scanf("%s %s",S,T)!=EOF)
    {
        k=strlen(T);
        for(i=strlen(T);i>0;i--)//向后移动
        {
            T[i]=T[i-1];    
        }
        T[0]=k;
        k=strlen(S);
        for(i=strlen(S);i>0;i--)//向后移动
        {
            S[i]=S[i-1];    
        }
        S[0]=k;
        printf("%d\n",Index_KMP(S,T));
    }
    return 0;
 
}
 

运行结果如下：

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