关于KMP算法的一些个人理解

KMP算法其实理解起来也不难，只不过很多过于公式化的讲解以及太过晦涩的说法会让人一头雾水；

KMP算法主要是判断一个字符串是否是另一个字符串的字串；对于这两个字符串，在算法描述中有固定的称谓：我们把最长的字符串称为text，需要判定的子串称为模式pattern;

对于这个问题，其实最容易想到的就是暴力枚举：即text字符串逐个字符判定，若当前第i字符和pattern首字符一样，进行pattern第二位的判定，如果中间有一个字符不同，则结束本轮判断，重新判断第i+1个字符；

该方法会达到O(m*n)级别；

而KMP算法就是处理该问题的更优算法，复杂度只有O(m+n);

其实我们可以大致推断出暴力枚举的缺陷点，其根本的问题就是回溯。由于pattern字符串有可能会有某些规律，使得我们判断第i个字符失败的时候，不用从i+1个开始重新判断，只需要判断i+k个，而KMP算法就是描述如何进行更优判断；

首先接触KMP算法，我们要理解NEXT数组，NEXT数组针对的是pattern字符串，描述的是当前字符串的最长的相同前缀和后缀的长度；

例如:ababa,其最长的相同前缀后缀就是aba，这个自己看一看就很清楚；

而NEXT数组保存的就是这些值。NEXT数组索引是当前0~i子字符串的长度，其相应的数组值就是该长度下的相同前后缀的长度k；

这里其实可以注意一下，由于给出的字符串坐标索引是从0开始，所以k也可以认为是最长前缀的最后一位的下标；

对于这个数组，我们其实可以依次算出来，但是如果用程序化的语言描述，则应该使用递推来进行；

具体代码如下：

void getNext(char s[],int len){
    int j=-1;
    next[0]=-1;
    for(int i=1;i<len;i++){
        while(j!=-1&&s[i]!=s[j+1]){
            j=next[j];
        }
        if(s[i]==s[j+1]){
            j++;
        }
        next[i]=j;
    }
}

对于上述代码，可能有点不清晰，所以讲解一下：

首先我们必定是从字符串开头算起，对于一个字符，我们无法计算他的前后缀，所以设置-1，意为，没有前后缀；

后续则从第二个字符进行判断；

首先理解j，j就是当前第i个字符需要比较的字符，为什么要比较，原因如下；

假如出现如下情况：

我们当前j指向的是b，需要比较的i指向的是b，如果这两个相同，则前缀后缀都变成了abb，其实j存在的意义就是判断能否继承之前的前后缀性质，既然i-1,i-2和j-1,j-2一样，都是ab，那么如果下一位i和j都一样，那么就是i,i-1,i-2和j,j-1,j-2一样，都为abb，则后缀前缀都变成abb；

之前说过，NEXT的内容代表的是相应长度下的最长前缀长度，因此，在相同的情况下，长度为i的串的前缀最大长度就应该是上述代码最后一行的next[i]=j；

相等情况下很好理解，关键在于不想等情况的理解；

自己参阅相关的文献。。。还想破头想了好久，发现不相等的情况其实就是两种情况的一种递归情况：

借用 该博客 下的一张图：

其实说白了，当不相等就是一个向左递归找更小的序列，看能不能使得子序列里能够出现相同的前缀后缀；

对于上述可能理解有点困难，可以举一个例子来看：

假如有一个字符串ccacbccace；

i指向e，j+1指向b；此时进行判断，不相等；

此时NEXT[j]就是ccac的最长前缀的最后一个索引，也就是1，这个时候在进行j+1和i的判断；

为什么要这样，原因在于根本来说，因为出去i和j，前缀和后缀相等，所以判断前缀ccac也就相当于判断后缀ccac，所以前缀ccac的第一个需要判断的c，该字符串的后缀也必定有；

当然，当时自己想到了另一种情况试图推翻，但是这种情况也无需考虑；

例如：ccabd,那么此时d前面不就和前缀不相同了？

其实这种情况不可能出现，因为前面j指向第二个c，所以比较的仍然是第一个元素；

所以总的来说，这就是一个递归向前的求更小前缀长度的操作。一旦向前得到的子序列有相同前缀和后缀，则第i个元素之前的后缀必定和该求得的前缀相同。否则，只能比较第一个元素，不可能得到更小的相同前缀后缀；

所以，next数组求解就很简单；

接下来就是ＫＭＰ算法，该算法就是利用NEXT函数求解；

说到底KMP算法就是利用pattern的前后缀来进行操作的。

如上所示：：

如果D和空格不匹配，此时由于ABCDAB有相同的前后缀所以替换的时候就把前缀和后缀重合，从而移动了j-next[j]个距离，从而到达以下位置：

所以也不难，主要是要怎么理解Next数组；

相应代码如下所示：

bool KMP(char text[],char pattern[]){
    int n=strlen(text),m=strlen(pattern);
    getNext(pattern,m);
    int j=-1;
    for(int i=0;i<n;i++){
        while(j!=-1&&text[i]!=pattern[j+1]){
            j=next[j];
        }
        if(text[i]==pattern[j+1]){
            j++;
        }
        if(j==m-1){
            return;
        }
    }
    return false;
}

如果需要重复计数：

int KMP(char text[],char pattern[]){
    int n=strlen(text),m=strlen(pattern);
    getNext(pattern,m);
    int j=-1;
    int ans=0
    for(int i=0;i<n;i++){
        while(j!=-1&&text[i]!=pattern[j+1]){
            j=next[j];
        }
        if(text[i]==pattern[j+1]){
            j++;
        }
        if(j==m-1){
            ans++;
            j=next[j];
        }
    }
    return ans;
}