KMP(2)

求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]的后缀

 比如上图中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

 这道题的大意是给你很多对模式串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]匹配继续

 以下是完整的代码:

#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的值就是答案

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P1439 最长公共子序列(LCS问题)

题目描述 给出1-n的两个排列P1和P2,求它们的最长公共子序列。 输入输出格式 输入格式: 第一行是一个数n, 接下来两行,每行为n个数,为自然数1-n的一个...

3234
来自专栏韦弦的微信小程序

Swift 加一 - LeetCode

语文能力捉急啊,看了半天没看懂。。。然后去找了英文原题(我实在LeetCode中文网做的题),英文描述如下:

663
来自专栏数据结构与算法

洛谷P3391 【模板】文艺平衡树(Splay)(FHQ Treap)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

2795
来自专栏趣学算法

数据结构 第8讲 KMP算法

j=5:T′="abaa",前缀为"a",后缀为"a",相等且l=1;前缀为"ab",后缀为"aa",不等;前缀为"aba",后缀为"baa",不等,因此nex...

762
来自专栏数据结构与算法

P2421 A-B数对(增强版)

题目背景 woshiren在洛谷刷题,感觉第一题:求两数的和(A+B Problem)太无聊了,于是增加了一题:A-B Problem,难倒了一群小朋友,哈哈。...

3449
来自专栏数据结构与算法

P3375 【模板】KMP字符串匹配(全程注释,简单易懂)

题目描述 如题,给出两个字符串s1和s2,其中s2为s1的子串,求出s2在s1中所有出现的位置。 为了减少骗分的情况,接下来还要输出子串的前缀数组next。如果...

2706
来自专栏python学习指南

python生成式

本篇将介绍Python的列表生成式,更多内容请参考:Python列表生成式 列表生成式即List Comprehensions,是Python内置的非常简...

1918
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之二维数组中的查找(九度OJ1384)

题目描述: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组...

1977
来自专栏mathor

子数组累加和为aim(小于等于aim)的三个问题

 这个和上面唯一的不同就是数组中只有正数,这里使用类似窗口移动的做法,给出两个指针,L,R表示窗口的左右边界 ,sum表示的是arr[L,R]之间的累加和,L,...

652
来自专栏大数据杂谈

【Excel】用公式提取Excel单元格中的汉字

1685

扫码关注云+社区