KMP算法总结

KMP算法关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

KMP算法的关键在于求算next[]数组的值，即求算A串的最长后缀与B串的前缀相同的长度，具体如下:

1. 令k代表B串开头所在的序号，j代表A串开头所在的序号，起始的时候j=1，k=0。

2. 我们比较一下B前串和A后串是否相等。首先比较A[j]==B[k],如果相等，那么next[j+1]=k+1，然后j++，k++。

关键就是理解这个next[j+1]=k+1，简单说就是A串中的第j+1个字符的next函数值由他前面的字符与B前串相等的个数来决定，就是说A串中的第j+1个字符的next函数值，是由他前面的字符串决定的。

3. 当A[j]!=B[k],即不相等的时侯，那么j不动，k返回到开头（因该是next[k]位置，便于理解先假设是返回k=0处），即从头比较B[0]与A[j]，B[1]与A[j+1].

例如：第 j+1 个字符的next函数值next[j+1]等于3，意味着它的前三个字符串，A[j-2]A[j-1]A[j]==B[0]B[1]B[2].

求next数组：

void Next(char str[], int len) {
    nex[0] = -1;
    int i = 0, j = -1;
    while (i < len) {
        if (~j && str[i] != str[j])
            j = nex[j];
        else nex[++i] = ++j;
    }
}

KMP匹配：

int KMP(char sa[], char sb[], int la, int lb) {
    Next(sb, lb);
    int i = 0, j = 0;
    while (i < la) {
        if (~j && sa[i] != sb[j])
            j = nex[j];
        else i++, j++;
    }
    return j;
}

例题:https://blog.csdn.net/lzyws739307453/article/details/97889297