【专题】KMP

发表于 2020-07-26 分类于专题，字符串本文字数： 1.9k 阅读时长 ≈ 3 分钟

字符串专题，介绍KMP算法

简介

Knuth-Morris-Pratt字符串查找算法，简称为“KMP算法”，常用于在一个文本串S内查找一个模式串T的出现位置。这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。时间复杂度O(|S|+|T|)。

朴素算法

给出一个最为常见的朴素字符串模式匹配算法，枚举文本串S的每一位，作为起点与模式串T进行匹配。时间复杂度O(|S|*|T|)。

int simple(char* s, char* t, int n, int m)
{
    int i = 0, j = 0;
    while (i < n)
    {
        if (s[i] == t[j]) {
            i++, j++;
            if (j >= m) {   // 匹配成功
                return i-j;
            }
        } else {
            i = i-j + 1;
            j = 0;
        }
    }
    return -1;
}

朴素算法的运行过程如下：

注意到，如下图，枚举以S[1]为起点，匹配到最后一个字符，S[4]!=T[3]，失配之后朴素做法是指针回退，以S[2]为起点开始下一轮匹配，即i=i-j+1, j=0。

毫无疑问，随着文本串S的长度增加，每一次回退重新匹配会花费大量的时间。那么有没有办法优化呢？

next数组

通过分析模式串T可以得到next数组，也可以当作fail数组理解。对于模式串T="abac"，当匹配到'c'时失配了，那么说明前面的"aba"已经匹配成功，"aba"最长的相等前缀后缀(不包括本身)是'a'，那么失配'c'后，我们可以跳过s[3]='a'（文本串S"aba"的后缀）与T[0]='a'（模式串T"aba"的前缀），直接匹配S[4]='b'与T[0]='b'。

为什么是最长的、相等的、不包括本身的前缀后缀呢？看下图自行理解。

由下表可以看出最长相等前缀后缀整体右移，首位加上-1，即是next数组。

模式串	a	b	a	c
最长相等前缀后缀	0	0	1	0
next数组	-1	0	0	1

next数组优化

对于失配时S[4]='c'与T[3]='b'不相等，由T[1]='b'与T[3]='b'相等，得出T[1]='b'与S[4]='c'也不相等，我们可以跳过这一步匹配。

注意C++中next是关键字（迭代器的一个函数），以及字符串下标从0开始和从1开始的代码稍有不同，注意必须求到next[|T|]，求字符串匹配数量以及最小循环节都需要用到。下面给出的是字符串下标从0开始的next数组的一种求法：

int nxt[mxn];

void getnxt(char* t, int m)
{
    int i = 0, j = -1; nxt[0] = -1;
    while (i < m)
    {
        if (j == -1 || t[i] == t[j]) {
            i++, j++;
            // if (t[i] == t[j])
            //     nxt[i] = nxt[j]; // next数组优化
            // else
                nxt[i] = j;
        } else
            j = nxt[j];
    }
}

KMP算法

有了next数组，下面给出KMP算法代码，与朴素算法类似，但是i不用回退了，可以看出求next数组的过程也是一个模式串T与自身匹配的过程。

int KMP(char* s, char* t, int n, int m)
{
    int i = 0, j = 0, ans = 0;
    while (i < n)
    {
        if (j == -1 || s[i] == t[j]) {
            i++, j++;
            if (j >= m) {   // 匹配成功
                return i-j;
            }
        } else
            j = nxt[j];
    }
    return -1;
}

KMP算法的运行过程如下：

最小循环节

参考 KMP模板，最小循环节。

定理：

假设S的长度为len，则S存在最小循环节，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。（1）如果len可以被len-next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。

index	0	1	2	3	4	5	6	7
char	a	b	c	d	a	b	c
next	-1	0	0	0	0	1	2	3

为方便说明，先设字符串的长度为len，循环子串的长度为L

例1 s0s1s2s3s4s5，next[6]=3 即s0s1s2=s3s4s5 很明显可知：循环子串为s0s1s2，L=len-next[6]=3，且能被len整除。

例2 s0s1s2s3s4s5s6s7，next[8]=6 此时len-next[8]=2，即L=2 由s0s1s2s3s4s5=s2s3s4s5s6s7 可知s0s1=s2s3，s2s3=s4s5，s4s5=s6s7 显然s0s1为循环子串

例3 s0s1s2s3s4s5s6，next[7]=4 此时len-next[7]=3，即L=3 由s0s1s2s3=s3s4s5s6 可知s0s1=s3s4，s2s3=s5s6 从而可知s0s1s2=s3s4s5，s0=s3=s6 即如果再添加3-4%3=2个字母（s1s2），那么得到的字符串就可以由s0s1s2循环3次组成

对于一个字符串，如abcd abcd abcd，由长度为4的字符串abcd重复3次得到，那么必然有原字符串的前八位等于后八位。也就是说，对于某个下标从0开始的字符串S，长度为len，由长度为L的字符串s重复R次得到，当R≥2时必然有S[0…len-L-1]=S[L…len-1]。

那么对于KMP算法来说，就有next[len]=len-L。此时L肯定已经是最小的了（因为next的值是前缀和后缀相等的最大长度，即len-L是最大的，那么在len已经确定的情况下，L是最小的）

模板

char s[mxn], t[mxn];
int nxt[mxn];

void getnxt(char* t, int m)
{
    int i = 0, j = -1; nxt[0] = -1;
    while (i < m)
    {
        if (j == -1 || t[i] == t[j]) {
            i++, j++;
            // if (t[i] == t[j])
            //     nxt[i] = nxt[j]; // next数组优化
            // else
                nxt[i] = j;
        } else
            j = nxt[j];
    }
}

int KMP(char* s, char* t, int n, int m)
{
    int i = 0, j = 0, ans = 0;
    while (i < n)
    {
        if (j == -1 || s[i] == t[j]) {
            i++, j++;
            if (j >= m) {
                // ans++;
                // j = nxt[j];
                return i-j;
            }
        } else
            j = nxt[j];
    }
    // return ans;
    return -1;
}

int main()
{
    scanf("%s %s", s, t);
    getnxt(t, strlen(t));
    for(int i=0; i<strlen(t); i++){
        printf("%d ", nxt[i]);
    }
    printf("\n");
    printf("%d\n", simple(s, t, strlen(s), strlen(t)));
    printf("%d\n", KMP(s, t, strlen(s), strlen(t)));
    return 0;
}