字符串之KMP详解

短命女 2022-05-30 10:08 185阅读 0赞

昨晚梳理了一下KMP的过程，感觉印象深刻了不少，在此写下博客加深印象，同时也希望能和大家交流。

KMP这个名字来源于其三个创始人名字首字母，主要用于解决字符串的匹配问题。

字符串的匹配问题：假设有两个字符串S和T，问串T是否出现在串S中/串T在串S中出现了多少次。(假设串S的长度为n，串T的长度为m)

常规思路：

按照我们正常的想法，肯定是用T跟S的每一位一一匹配，一旦遇到不能匹配的时候，就将正在匹配的起始位置右移一个，即起始位置+1，然后依然与T进行一一匹配，直到匹配成功为止，否则T不出现在S中。

这样思路的时间复杂度为O(n\*m),那么有没有好一点的方法来解决这个问题呢，嘤，当然有，就是众所周知的KMP了。

KMP算法思路：

首先我们设S串(称为主串)为S1S2S3......Sn(S0不存放字符)

设T串(模式串)为T1T2T3......Tm

假设我们对两个串进行匹配，匹配到如下过程:

![Center][]

Si和Tj不匹配了，按照上面的常规思路就是将下边(i-j+1)加上一，再一一匹配了，但是我们的KMP不这样

举个栗子，假设主串为abacabadaea，模式串为abad，我们先模拟一下常规思路的匹配过程：

![20180309211818899][]

![20180309212749409][]

我们可以看到，在上面的五次匹配过程中，第二次第四次匹配是完全没有必要的，第一次匹配不成功之后直接进行第三次匹配，再进行第五次匹配即可得到结果。

也就是说，主串当前匹配的字符可以不做移动，直接将模式串右移，因为第一次匹配的时候S3和T3已经匹配成功了，而T3又与T1相等所以我们可以将S4直接与T2进行匹配，这样就减少了不必要的匹配次数。

通俗的讲，假设有主串和模式串已经匹配到下面的样子了

![20180310103231977][]

要在模式串T中找一个位置k(k<j)来跟si匹配，这时要确保T1...Tk-1==Si-k+1...Si-1

由之前的匹配可知Tj-k+1...Tj-1==Si-k+1...Si-1

所以我们只需要找到一个k，使得T1...Tk-1==Tj-k+1...Tj-1就行,这时匹配就分别从主串的Si、模式串的Tk开始了

令next\[j\]=k，则next\[j\]表示模式串中第j个字符与主串中相应字符“失配”时，在模式串中需要重新和主串中该字符进行比较的字符位置。（next被称为前缀表）

所以我们可以得到模式串的定义：

当j=1时，next\[j\] = 0;

当1<k<j且T1...Tk-1==Tj-k+1...Tj-1时(不为空)，next\[j\] = max\{k\}；

其他情况下，next\[j\] = 1；

求得next数组后，就可以根据上面的分析来求解匹配情况了。

那么，如何求得next数组呢？

我们先看看模式串abaabcac的next数组的情况：

![20180310104955796][]

首先我们可以保证next\[1\] = 0，假设next\[i\] = k，该如何求next\[i+1\]呢？

如果T\[i\] = T\[k\]的话，那么next\[i+1\] = next\[i\]+1 = k+1；

如果T\[i\] != T\[k\]， 就继续判断T\[i\] 是否等于 T\[next\[k\]\] 知道找到等于或next\[k\] = 0为止，如果找到等于，令next\[i+1\] = next\[next\[..i..\]\]+1,反之如果next\[next\[..i..\]\] == 0, next\[i+1\] =1。

即求得next数组。

另外对求next数组还有一个优化问题，如主串为aaabaaaaab，模式串为aaaab，那模式串的next数组如下：

![20180310112253372][]

其实按照之前对next数组的定义，next\[2\] = 1,next\[3\] = 2, next\[4\] = 3, next\[5\] = 4,但是因为T\[next\[j\]\] == T\[j\]，就没有与S\[i\]比较的必要了，所以可以一直往前找next\[j\]。

以上是我对KMP的理解，如有理解不当之处，欢迎指出。

//去吃个饭，吃完饭给出代码

参考代码:

#include<cstdio>
    #include<cmath>
    #include<cctype>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<stack>
    #include<queue>
    #include<map>
    #include<set>
    #include<list>
    #include<vector>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    const int maxm = 1e4+10;
    const int maxn = 1e6+10;
    int n,m;
    char s[maxn];
    char t[maxm];
    int next[maxm];
    //求前缀表(next数组)
    void GetNext()
    {
        next[0] = -1;
        int i = 0;
        int j = -1;//next[i]
        while( i < m)
        {
            if( j == -1 || t[i] == t[j])
            {
                i++;
                j++;
                if( t[i] != t[j])
                    next[i] = j;
                else
                    next[i] = next[j];
            }
            else
                j = next[j];
        }
     //   for( int i = 0; i < m; i++)
     //       printf("%d ",next[i]);
     //   puts("");
    }
    //求模式串在主串中出现的次数
    int KMPCount()
    {
        GetNext();
        int ans = 0;
        int i = 0;
        int j = 0;
        while( i < n)
        {
            if( j == -1 || s[i] == t[j])
            {
                i++;
                j++;
            }
            else
                j = next[j];
            if( j == m)
            {
                ans++;
                j = next[j];
            }
        }
        return ans;
    
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while( T--)
        {
            scanf("%s%s",t,s);
            n = strlen(s);
            m = strlen(t);
            int ans = KMPCount();
            printf("%d\n",ans);
        }
    
        return 0;
    }

以上

[Center]: /images/20220530/439d27c9b8d24e33a9e5c940050dcba4.png
[20180309211818899]: /images/20220530/b22c574ac0bc407db6de60434f5f9ce3.png
[20180309212749409]: /images/20220530/d08cce08ff78427c8fc347abaae2dfaa.png
[20180310103231977]: /images/20220530/75766e7840b44434be92e6a18041091c.png
[20180310104955796]: /images/20220530/0bcce86f4a5d48b1af0af81af3b73207.png
[20180310112253372]: /images/20220530/52a829be020b4387844a9b6ef3ba734c.png