（转载）KMP算法讲解

网上找到了一篇详细讲解KMP字符串匹配算法，质量很高。特备忘于此。

摘自：http://blog.csdn.net/v_july_v/article/details/7041827

实现代码如下：

//@http://blog.csdn.net/v_july_v/article/details/7041827

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int next[];

void GetNextval(char* p, int next[])

{

    int pLen = strlen(p);

    next[] = -;

    int k = -;

    int j = ;

    while (j < pLen - )

    {

        //p[k]表示前缀，p[j]表示后缀

        if (k == - || p[j] == p[k])

        {

            ++j;

            ++k;

            //较之前next数组求法，改动在下面4行

            if (p[j] != p[k])

                next[j] = k;   //之前只有这一行

            else

                //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]

                next[j] = next[k];

        }

        else

        {

            k = next[k];

        }

    }

}

int KmpSearch(char* s, char* p)

{

    int i = ;

    int j = ;

    int sLen = strlen(s);

    int pLen = strlen(p);

    while (i < sLen && j < pLen)

    {

        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++

        if (j == - || s[i] == p[j])

        {

            i++;

            j++;

        }

        else

        {

            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]

            //next[j]即为j所对应的next值

            j = next[j];

        }

    }

    if (j == pLen)

        return i - j;

    else

        return -;

}

int main()

{

    char *s="BBC ABCDAB ABCDABCDABDE";

    char *p="ABCDABD";

    GetNextval(p, next);

    printf("kmp search: %d\n", KmpSearch(s, p));

    return ;

}