KMP算法

2024/7/12 OI 字符串 OI C++

1.引入

现在有两个字符串$A$和$B$，求$B$是否是$A$的子串，如果是，输出第一个匹配的位置$(len_A = n\quad len_B = m)$

$A = bacbababaabcbab$

$B = ababaca$

朴素算法

对于朴素算法，也就是暴力，我们将$B$的每一位于$A$进行比较。这里使用两个指针$i, j$表示匹配到$A$和$B$的哪一位。如果$A[i] == B[j]\quad i,j$,同时加一，如果不相等，则将$B[1]$与$A[i]$进行比较。如此重复，即可完成。当$j == m$时，表示匹配完成，输出$i - j + 1$。

但是对于朴素算法,最坏情况下，时间复杂度会达到$O(mn)$~~sb才会这么写~~。于是，我们KMP的作用就来了！！！！！

让我们热烈欢迎！！！！

2.KMP算法概述

KMP算法则是一种时间复杂度十分优秀的算法，即使在最坏情况下，时间复杂度也能达到线性也就是$O(n)$。

考虑为什么朴素算法那么慢

当在这种情况时：

$b,a,c,b,a,b,a,b,a,a,b,c,b,a,b$

$\qquad ;,a,b,a,b,a, c ,a$

此时若$i = 9, j = 5$会发现$A[i + 1]$和$B[j + 1]$不匹配，作为朴素算法，会将$A[6]$与$B[1]$进行比较，但是，我们发现$A[1-3]$和$B[6-9]$是完全相等的，KMP算法就会将$B$后移两位，直接将$A[10]$和$B[4]$进行比较这样就能大大节省时间。

形式化的讲：

此时$A[s + 1…s+k]$和$B[1…k]$匹配上了，但是$A[s+k+1]$和$B[k+1]$不匹配

朴素算法：是将$A[s+2]$和$B[1]$重新比较。

KMP算法：是寻找一个最大的$x$使得$A[s+1…s+k]$的后$x
$个字符和$B[1…k]$的前$x$个字符匹配。对于这部分，可以不用判断。

更具体的，由于$A[s + 1…s+k]$和$B[1…k]$匹配上了，即$A[s + 1…s+k]==B[1…k]$，那么我们寻找$x$的过程，就是寻找一个尽可能大的$x$使得$B$的前$x$个字符等于$B$的后$x$个字符。我们记$x=next[k],x<k$。

对于本文出现的$B$串，我们可以构建一个$next$数组，$next[,]={0,0,1,2,3,0,1}$，若$A[s + 1…s+k]==B[1…k]$且$A[s+k+1]\neq B[k+1]$，那么我们将$A[s+k+1]$与$B[next[k]+1]$进行比较，直到$A[s+k+1]$与$B[next[k]+1]$相等或$next[k]==0$

void KMP()
{
    int j = 0;
    for(int i = 1; i <= n; i++)
    {
        while(j > 0 && B[j + 1] != A[i])
            j = next[j];
        if(B[j + 1] == A[i])
            j++;
        if(j == m)
            j = next[j];//匹配完成，寻找下一处匹配
    }
}

构建$next$数组的过程，其实就是模式串自我匹配的过程，代码与KMP过程很像

void getnext()
{
    int k = 0;
    next[1] = 0;
    for(int i = 2; i <= m; i++)
    {
        while(k > 0 && B[k + 1] != B[i])
            k = next[k];
        if(B[k + 1] == B[i])
            k++;
        next[i] = k;			
    }
}

P3375

P4391

完结撒花！！！

看在我写博客的份上，dalao赏一个赞呗！

LOADING