kmp下载

时间：2019-09-25 11:40:07 作者：无名浏览量：60

KMPlayer 4.2.2.28 中文版
大小：36.14 MB
日期：2019/9/25 11:40:07
环境：WinXP, Win7, Win8, Win10, WinAll

今天小编就为大家带来KMP下载的相关资讯。KMP所需GOTO的下一个比较位置，整理出来一个next数组，然后在上面的算法中使用。

定义

一种由Knuth(D.E.Knuth)、Morris(J.H.Morris）和Pratt(V.R.Pratt）三人设计的线性时间字符串匹配算法。这个算法不用计算变迁函数δ，匹配时间为Θ（n），只用到辅助函数π[1，m]，它是在Θ（m）时间内，根据模式预先计算出来的。

数组π使得我们可以按需要，“现场”有效的计算（在平摊意义上来说）变迁函数δ。粗略地说，对任意状态q=0，1，…，m和任意字符a∈Σ，π[q]的值包含了与a无关但在计算δ（q，a）时需要的信息。由于数组π只有m个元素，而δ有Θ（m∣Σ∣）个值，所以通过预先计算π而不是δ，使得时间减少了一个Σ因子。

kmp下载

kmp下载图一

详细阐述

next数组的理解与计算

首先声明在不同的地方对next数组的定义和计算有所不同，为了避免混淆，在此仅介绍一种。

next数组是对于模式字符串也就是需要被匹配字符串其中的每一个字母而言，为了在匹配时避免重复判断而存在，下面通过一个实例来介绍next数组的意义和具体用法。

首先摆出next数组

kmp下载

kmp下载图二

a 匹配串：b a b a b b；

0 0 1 2 3 1；

列如 s原串：b a b a b a b c b a b a b a b a b b；

a匹配串：b a b a b b；

先按暴力匹配可以得到如下

原串：b a b a b a bcb a b a b a b a b b；

匹配串 b a bab b；

在如图黑色字母处出现不匹配，如果继续暴力，则会将匹配串向后移一位，然后再重新将匹配串的指针指向首位重新开始逐个匹配。但现在思考一下，我已经匹配了过了前三个字符了，可不可以合理地利用已知的条件呢？

next数组就起到了运用已知条件的作用。如next[2]=1（从0开始），代表从匹配串队首开始向后走1（包括此点）与从a[2]开始向前走1的字符串完全相同。如next[3]=2，代表a[0]，a[1]所组成的字符串与a[2]a[3]组成的完全相同。next[n]就代表n满足上述条件的长度。

这样的话next数组的求解就十分容易了，只需o（n）的复杂度；next[0]必为0，对于求解next[n]，采用递推思想，如果next[n]=k;(k>0)则必须next[n-1]=k-1;如果next[n-1]=0;则看next[n]是否等于next[0]。如等于则next[n]=1。

kmp下载

kmp下载图三

接下来就是实现时next数组的现实作用了，如上图，设原串的指针为i，匹配串的指针为j。当匹配到a[3]失败时，要注意因为从a[j]即a[3]开始向前走next[j-1]，即1与从队首开始向后走next[j-1]的字符是相同的，所以j回到next[j-1]，即a[1]的位置，而i指针不变，再进行比较。这样就能高效地进行匹配。

结合图像来看，如右下图加黑的B与A部分就是匹配失败时next[j-1]的值代表B部分与A部分完全相同，所以直接跳过这部分，直接将j指针移到A部分的后一位处，即next[j-1]处。