KMP算法的简单实现

KMP的工作原理

阮一峰的博客讲的非常好
点击访问!!

KMP的代码实现

动态规划求解NEXT

这里设NEXT数组等价最长公共前后缀数组(非经过平移加一的NEXT数组)
设当前要求解NEXT[q]，同时已经求出了 NEXT[i](i < q)

1. 如果P[q] == P[k](k == NEXT[q-1])，直接k++使最长匹配前后缀增长一位
2. 如果P[q] != P[k]，则取k = NEXT[K - 1]，这是因为当前最长匹配无法继续增长，找次最长匹配继续尝试(画个图就明白了)。

void makeNext(const char P[],int next[])
{
    int q, k;
    int m = strlen(P);
    next[0] = 0;
    for (q = 1, k = 0; q < m; ++q)
    {
        while(k > 0 && P[q] != P[k])
            k = next[k - 1];
        if (P[q] == P[k])
        {
            k++;
        }
        next[q] = k;
    }
}

手动计算NEXT的过程

KMP匹配
当前项相等继续匹配下一个字母
不相等取NEXT数组相应的值移动带匹配数组

int kmp(const char T[],const char P[],int next[])
{
    int n, m;
    int i, q;
    n = strlen(T);
    m = strlen(P);
    makeNext(P,next);

    for (i = 0, q = 0; i < n; ++i)
    {
        while(q > 0 && P[q] != T[i])
            q = next[q - 1];
        if (P[q] == T[i])
        {
            q++;
        }
        if (q == m)
        {
            printf("Pattern occurs with shift:%d\n",(i-m+1));
        }
    }    
}