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

相关文章

来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1142
来自专栏码匠的流水账

spring security reactive获取security context

本文主要研究下reactive模式下的spring security context的获取。

1752
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1786
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

702
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2169
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2478
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2818
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

5866
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2232

扫码关注云+社区