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 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

每天一算:Evaluate Reverse Polish Notation

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出该题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

601
来自专栏微信公众号:Java团长

Java泛型详解

定义了一个List类型的集合,先向其中加入了两个字符串类型的值,随后加入一个Integer类型的值。这是完全允许的,因为此时list默认的类型为Object类型...

832
来自专栏恰同学骚年

剑指Offer面试题:13.调整数组顺序使奇数位于偶数前面

  例如有以下一个整数数组:12345,经过调整后可以为:15342、13542、13524等等。

1026
来自专栏静默虚空的博客

排序五 简单选择排序

要点 简单选择排序是一种选择排序。 选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。 简单排序处理流程 ...

1969
来自专栏技术沉淀

Python: 函数式编程

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

06:整数奇偶排序

06:整数奇偶排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定10个整数的序列,要求对其重新排序。排序要求: 1...

3206
来自专栏小樱的经验随笔

C/C++中连接函数strcat的应用(简单讲解)

有位学弟问到我如何将两个字符连接起来,想想java/python里面可以直接用+连接起来,可是C/C++里面有没有这么方便的做法呢?

922
来自专栏小樱的经验随笔

hihoCoder 1039:字符消除(字符串处理)

#1039 : 字符消除 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi最近在玩一个字符消除游戏。给定一个只包含大写字母"A...

2938
来自专栏Vamei实验室

Python进阶06 循环对象

这一讲的主要目的是为了大家在读Python程序的时候对循环对象有一个基本概念。 循环对象的并不是随着Python的诞生就存在的,但它的发展迅速,特别是Pytho...

1907
来自专栏SeanCheney的专栏

《Pandas Cookbook》第03章 数据分析入门1. 规划数据分析路线2. 改变数据类型,降低内存消耗3. 从最大中选择最小4. 通过排序选取每组的最大值5. 用sort_values复现nl

1242

扫码关注云+社区