MENU

KMP(2)

July 2, 2018 • Read: 220 • 算法

求next数组(暴力版本)

Next[0] = -1
Next[1] = 0
For i = 2...P.len
    Next[i] = 0;
    For j = i - 1...1
        If P[1...j] == P[i - j + 1...i]//P[1...j]是P[1...i]的后缀
            Next[i] = j
            Break

不过上面这个根据定义直接求的算法时间复杂度太高了。如果不优化会成为整个KMP的瓶颈,导致还不如直接用O(P.len * S.len)的暴力算法匹配效率高。要优化求next数组的算法,就需要对next数组有深入的理解。首先要理解,next实际上描述了P的所有前缀字符串两两之间的一种关系

举个例子,P=”bababb”,则P一共有6个前缀,依次是”b”,“ba”, “bab”, “baba”, “babab”, “bababb”。在这6个字符串中,如果P[1..k]恰好是P[1..j]的后缀,我们就连一条从P[1..j]到P[1..k]的虚线,表明这种后缀关系。显然这种后缀关系是一个偏序关系,也就是说如果P[1..i]是P[1..k]的后缀,而P[1..k]是P[1..j]的后缀,那么P[1..i]一定也是P[1..j]的后缀

image

比如上图中P[1..1](”b”)是P[1..3](”bab”)的后缀,P[1..3](”bab”)是P[1..5](”babab”)的后缀。 所以P[1..1] (”b”)也是P[1..5] (”babab”)的后缀。特别的,如果P[1..k]是P[1..j]最长的后缀,我们就连一条从P[1..j]到P[1..k]的实线,表明这种最长后缀关系

这个实线表明的”最长后缀关系“,实际上就是next数组。比如P[1..6]指向P[1]对应next[6]=1;P[1..5]指向P[1..3]对应next[5]=3。而且如果我们想知道都有哪些前缀是P[1..j]的后缀,只需要沿着实线也就是next数组往上找即可:P[1..next[j]], P[1..next[next[j]]], P[1..next[next[next[j]]]], … Ø。此外,如果P[1..k]是P[1..j]的后缀,那么各自砍掉最后一个字母后,P[1..k-1]仍是P[1..j-1]的后缀

有了以上两条分析结果,我们就可以来求next数组了。首先令next[0]=-1, next[1]=0。然后我们用递推法依次求出每一个next[j]。假设我们已经求出来next[0], next[1], … next[j],现在要求next[j+1]

假设next[j+1]的值是k,那么P[1..k]就必须是P[1..j+1]的后缀,所以P[1..k-1]就必须是P[1..j]的后缀(都砍掉最后一个字符)。而之前我们分析得出P[1..j]的后缀分别是P[1..next[j]], P[1..next[next[j]]], P[1..next[next[next[j]]]], … Ø;所以如果next[j+1]不等于0的话,next[j+1]就只可能是next[j]+1或者next[next[j]]+1或者next[next[next[j]]]+1… 或者1

而我们要求next[j+1],就要在集合{ next[j]+1,next[next[j]]+1,next[next[next[j]]]+1,…… 1}中找到一个最大的数k,满足P[k]==P[j+1]。如果这样的k存在,那么next[j+1]=k;否则next[j+1]=0

j = Next[0] = -1
For i = 1...P.len
    While j >= 0 AND P[j + 1] != P[j]
        j = next[j]
    Next[i] = ++j

下面看一下KMP求匹配的完整代码:

#include <cstring>
#include <cstdio>
using namespace std;
int next[1000001];
int ans;
char p[1000001],s[1000001];
int n,m;
int main()
{
    ans = 0;
    scanf("%S%S",p + 1,s + 1);
    n = strlen(s + 1);
    m = strlen(p + 1);
    next[0] = -1;
    int j = -1;
    for(int i = 1;i <= m;i++)
    {
        while(j >= 0 && p[j + 1] != p[i])
            j = next[j];
        next[i] = ++j;
    }
    j = 0;
    for(int i = 1;i <= n;i++)
    {
        while(j >= 0 && p[j + 1] != s[i])
            j = next[j];
        ++j;
        if(j == m)
        {
            ans = i - m + 1;
            break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

首先要注意上面代码中字符串都是从P[1]和S[1]开始的,并不是从下标0开始。并且n和m分别是S的长度和P的长度。第16-21行是在求next数组。第23-33行是在进行KMP匹配。注意其中第28-32行,如果匹配已经进行到j==m,说明P的最后一个字符P[m]也匹配上了,并且匹配到的是S[i]。这里我们是要在S中找P第一次出现的位置,也就是P[1]的位置,所以是i-m+1

例1 题目链接:hihoCoder1015

image

这道题的大意是给你很多对模式串P和原串S。对于每一对都让你求出P在S中出现了多少次。需要注意出现的P是可以部分重叠的,比如ADA在ADADADA中出现了3次

之前KMP的代码是找到第一次出现的位置就中止了。现在我们需要让KMP在找到一次完整的匹配之后还能继续匹配下去。让匹配继续进行的方法就是,当P[m]匹配S[i]成功时,(这里m是P的长度)令j=next[m],然后从尝试S[i+1]和P[j+1]匹配继续
image
以下是完整的代码:

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int nxt[1000001];
int ans,t;
char p[1000001],s[1000001];
int n,m;
int main()
{
    cin >> t;
    while(t--)
    {
        ans = 0;
        scanf("%s%s",p + 1,s + 1);
        n = strlen(s + 1);
        m = strlen(p + 1);
        nxt[0] = -1;
        int j = -1;
        for(int i = 1;i <= m;i++)
        {
            while(j >= 0 && p[j + 1] != p[i])
                j = nxt[j];
            nxt[i] = ++j;
        }
        j = 0;
        for(int i = 1;i <= n;i++)
        {
            while(j >= 0 && p[j + 1] != s[i])
                j = nxt[j];
            if(++j == m)
            {
                ans++;
                j = nxt[j];
            }
        }
        cout << ans << endl;
    }
    return 0;
}

首先是c++11中std::next是有定义的,所以为了提交到hihoCoder上不会编译出错,我们把next[]数组的名字改成nxt[]

然后就是第31-35行,这里匹配到j==m说明完成了一个完整匹配之后,我们令j=nxt[j],就可以让KMP继续找下一个完整匹配的位置。最后ans的值就是答案

最后编辑于: October 10, 2018
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment