字符串匹配KMP算法最正确算法，网上很多算法都有bug，导致误导很多人

最近网上看KMP算法，看了很多作者写的文章，后来发现看不明白，貌似哪里不正确，把代码拷下来运行发现也有问题，导致误导了很多人，我先举几个例子：

1. https://www.cnblogs.com/yjiyj...
2. 某人python代码

def kmp(string, match):
    n = len(string)
    m = len(match)
    i = 0
    j = 0
    count_times_used = 0
    while i < n:
        count_times_used += 1
        if match[j] == string[i]:
            if j == m - 1:
                print "Found '%s' start at string '%s' %s index position, find use times: %s" % (match, string, i - m + 1, count_times_used,)
                return
            i += 1
            j += 1
        elif j > 0:
            j = j - 1
        else:
            i += 1

代码很简洁，但是输入：

kmp("abcdeffg", "abcdefg")

明显匹配不到，但是还是会得到结果。

拜读《算法导论》后，才将疑惑解除。

下面是正确的代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LEN 100

int * getnext(const char * pattern);

int main()
{
        char string[MAX_LEN];
        char pattern[MAX_LEN];

        int *next;

        scanf("%s", string);
        scanf("%s", pattern);

        int slen = strlen(string);
        int plen = strlen(pattern);

        if(plen > slen || slen > MAX_LEN || plen > MAX_LEN)
        {
                exit(0);
        }

        next = getnext(string);

        int q = -1;

        for(int i = 0; i < slen; i++)
        {
                while(q >= 0 && pattern[q+1] != string[i])
                {
                        q = next[q];

                }
                if(pattern[q+1] == string[i])
                {
                        q++;
                }
                if(q == plen - 1)
                {
                        printf("pattern occurs with shift %d\n", i + 1 - plen);
                        q = next[q];
                }
        }

        return 1;
}

int * getnext(const char * pattern)
{
        int plen = strlen(pattern);

        int *next = (int *)malloc(MAX_LEN * sizeof(int));

        next[0] = -1;

        int k = -1;

        for(int j = 1; j < plen; ++j)
        {

                while(k >= 0 && pattern[j] != pattern[k+1])
                {
                        k = next[k];
                }

                if(pattern[k+1] == pattern[j])
                {
                        k++;
                }

                next[j] = k;
        }

        return next;
}

运行结果：

abcdefghijkkkkkkkkkllllll
k
pattern occurs with shift 10
pattern occurs with shift 11
pattern occurs with shift 12
pattern occurs with shift 13
pattern occurs with shift 14
pattern occurs with shift 15
pattern occurs with shift 16
pattern occurs with shift 17
pattern occurs with shift 18