2017-08-07

kmp算法

文章目录

原文地址:https://ngunauj.github.io

之前的一片博客已经谈到了kmp,kmp应该是我在课堂上学习的第一个算法。当时对这个了解的并不是很深，而且比赛的时候直接套板子就行了。今天重新看了一遍这个算法，古人云：温故而知新，可以为师。

kmp算法也是用来处理字符串匹配问题的，如之前将的字符串哈希算法，可以用来判断某个字符串是否在另一个字符串中，可以统计字符串a在字符串b中出现的次数，kmp中的next数组可以用来求当前串的前缀和和后缀相等的最大长度。

1.kmp思想

当两个字符串进行匹配的时候，最暴力的方法是O(nm)的算法，如用字符串哈希可以达到O(m+n)，kmp也可以达到O(m+n)而且理论上kmp要比字符串哈希快。那么这里我们要解释一下为什么kmp时间复杂度为O(m+n)。
假设字符串T的长度为n,字符串P的长度为m，m<=n,现在我要判断T是否包含P。暴力的方法当然是，依次枚举T的每一位，如果T[i] == P[0]那么我们就进行T[i+1] 和 P[1]的比较，一次类推，如果在某个位置如T[i+5] 和 P[5]不匹配了,那么我们只能从P[0]开始重新比较，那么这样，最坏的时间复杂度为O(nm)。事实上如果我们提前计算出 P[5]和T[i+5]不匹配时，从P[x]开始重新匹配，那么时间复杂度将会降到O(n+m)。而提这个提前计算的过程就是计算next数组的过程。

2.next数组

next数组表示的是长度，下标从1开始，但是在遍历原字符串时，下标还是从0开始。假设我们现在已经求得next[1]、next[2]、……next[i]，分别表示长度为1到i的字符串的前缀和后缀最大公共长度，现在要求next[i+1]。

由上图我们可以看到，如果位置i和位置next[i]处的两个字符相同（下标从零开始），则next[i+1]等于next[i]加1。如果两个位置的字符不相同，我们可以将长度为next[i]的字符串继续分割，获得其最大公共长度next[next[i]]，然后再和位置i的字符比较。这是因为长度为next[i]前缀和后缀都可以分割成上部的构造，如果位置next[next[i]]和位置i的字符相同，则next[i+1]就等于next[next[i]]加1。如果不相等，就可以继续分割长度为next[next[i]]的字符串，直到字符串长度为0为止。类是dp。
这里举个例子求字符串：P:abcabcabcda的next数组。

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

P的next素组为0,0,0,1,2,3,4,5,6,0,1

3.代码实现

下面给出一个字符串里有几个另一个字符串（可重叠和不可重叠两种）的示例代码
(1)可重复

#include<stdio.h>
#include<string.h>
void makeNext(const char P[],int next[]) {
    int i,j;
    int m = strlen(P);
    next[0] = 0;
    for (i = 1,j = 0; i < m; ++i) {
        while(j > 0 && P[i] != P[j])
            j = next[j-1];
        if (P[i] == P[j]) {
            j++;
        }
        next[i] = j;
    }
}
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));
        }
    }
}
int main() {
    int i;
    int next[20]={0};
    char T[] = "ababababaaaaaaa";
    char P[] = "abcabcabcda";
    printf("%s\n",T);
    printf("%s\n",P );
    // makeNext(P,next);
    kmp(T,P,next);
    for (i = 0; i < strlen(P); ++i){
        printf("%d ",next[i]);
    }
    printf("\n");
    return 0;
}

(2)不可重复

#include<stdio.h>
#include<string.h>
void makeNext(const char P[],int next[]) {
    int i,j;
    int m = strlen(P);
    next[0] = 0;
    for (i = 1,j = 0; i < m; ++i) {
        while(j > 0 && P[i] != P[j])
            j = next[j-1];
        if (P[i] == P[j]) {
            j++;
        }
        next[i] = j;
    }
}
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));
            q = 0;
        }
    }
}
int main() {
    int i;
    int next[20]={0};
    char T[] = "ababababaaaaaaa";
    char P[] = "abcabcabcda";
    printf("%s\n",T);
    printf("%s\n",P );
    // makeNext(P,next);
    kmp(T,P,next);
    for (i = 0; i < strlen(P); ++i){
        printf("%d ",next[i]);
    }
    printf("\n");
    return 0;
}