文档章节

KMP算法中get_next函数分析

JoshSone
 JoshSone
发布于 2017/05/16 11:45
字数 1998
阅读 220
收藏 0

看了网上几个号称最简单的KMP算法分析,也都云里雾里,对于KMP的基本思想我还是略微了解的,但是get_next函数中(无论何种写法,总会有这种回溯的思想)j=next[j],我总是怀有疑问,为什么每次回溯的步长是next [j] ?

我们先看get_next函数的代码:

get_next函数:

void get_next(int T[],int next[]){
    int i=0;
    next[0]=-1;
    int j=-1;
    while (T[i]!='\0') {
        if (j==-1||T[i]==T[j]) {
            i++;j++; next[i]=j;
        }else{
            j=next[j];
        }
    }
}

首先要明白几个概念:

前缀和后缀:前缀就是从第0位开始,往后连续的子串,后缀就是从最后一位为结尾,往前连续的子串(前后缀不包含字符串本身)

例如:a b c a b  ; a是它的前缀 , a b也是,a b c也是,同理b是它的后缀,a b也是它的后缀,c a b也算(但是a b c a b既不是前缀也不是后缀)

最长的相同前缀和后缀:a b c a b 当前缀为a b,后缀为a b时,是它的最长相同前缀和后缀

最长相同前后缀的长度:上面例子中最长相同前后缀的长度就是2

再明白几个变量的意义:

i:i是一个位置指针,移动过程就是从左到右,依次增加,T [i]代表的就是T的第i位字符(从0开始)

next [i]:代表第0位到i-1位的最长相同前后缀的长度

j:j代表的意义比较多样,我们可以看到函数中j又用来当做位置指针(如:T[i]与T[j]进行比较),又用来当做最长相同前后缀的长度(如:用来给next[i]进行赋值),最奇怪的是还用next[j]给自身赋值(如:j=next[j],这里其实是一个回溯的过程,j作为回溯的步长,下面会讲到)短短的几行代码,j简直了,无所不能,哪都有他,你咋不上天呢?我们接下来会着重分析一下j到底为什么这么牛X。

我们的规则是:

i:一直往后走

j:如果发现字符串第j位与第i位相同,那么j就+1,也就是往后走一位,然后新的j位与新的i位再进行比较,如果再相同就再往后走一位,依次进行,如果比较到两个字符不同,则j进行回溯,j回到某一个位置,再与i进行比较,总之我们要确保j所在的位置,能保证0~j-1位能和i-j+1~i位字符一一对应

举个栗子: T: a b c a b b c

i

0 1 2 3 4 5 6
T a b c a b b c
next -1            

我们默认next[0]=-1,i=2时,我们要考察的是0~1位,也就是a b的最长相同前后缀的长度,显而易见next[2]=0;

i

0 1 2 3 4 5 6
T a b c a b b c
next -1 0 0        

 

接下来观察i=4时,也就是考察0~3位,a b c a的最长相同前后缀,也就是字符a,长度为1,next[4]=1;

i

0 1 2 3 4 5 6
T a b c a b b c
next -1 0 0 0 1    

 

接下来依次进行:

i

0 1 2 3 4 5 6
T a b c a b b c
next -1 0 0 0 1 2 0

我们再结合代码:分析上述过程

  第一次循环 初始值:i=0 j=-1;         改变后的值:  i=1,j=0,next[1]=0

  第二次循环 初始值:i=1  j=0;          改变后的值:  j=next[0]=-1

  第三次循环 初始值:i=0 j=-1;       改变后的值:  i=2,j=0,next[2]=0

  第四次循环 初始值:i=2 j=0;        改变后的值:  j=next[0]=-1

  第五次循环 初始值:i=2  j=-1;      改变后的值:  i=3,j=0,next[3]=0

那么我们就发现了一个规律,似乎每当T[j] != T[i]时,next[i+1]总是等于0

如果真的是这样代码就可以写成:

void get_next(int T[],int next[]){
    int i=0;
    next[0]=-1;
    int j=-1;
    while (T[i]!='\0') {
        if (j==-1||T[i]==T[j]) {//②这时j==-1
            i++;j++; next[i]=j; //③i++,j+1=0,next[i]=0
        }else{
            j=-1;//①如果要是T[i]!=T[j],那么我们就直接让j=-1
        }
    }
}

 这是一定的吗?

再举一个栗子:

i

0 1 2 3 4 5 6
T a a b a a a c
next -1 0 1 0 1 2 ?

我们按照之前的经验

i=4,j=0时,也就是考察0~3位,a a b a,最长相同前后缀是a,这时i++,j++

i=5,j=1时,考察0~4位,a a b a a,最长前后缀是a a ,i++,j++

i=6,j=2时,考察0~5位,a a b a a a,这时T[2] != T[6],也就是说'b'!='a',那么T[6]是不是应该等于0了呢?

但是我们可以看出,虽然T[2] != T[6] ,可T[0~1]==T[4~5],也就是说next[6]=2

当我们的前缀和后缀在一段时间内处于一一对应的状态,即T[0~1]和T[3~4],但T[2]和T[5]不相等,我们不能直接判断next[6]=0,因为这时可能以T[5]为结尾的后缀,能找到一个对应相等的前缀

我们思考一般情况

上面代表,当T[0 ~ j-1]==T[i-j ~ i-1],但T[j] !=T [i]时的情况

这时如果可以找到A段中的子串,Ak段(T[0~k-1])与包含第i位在内的T[i-k+1,i]相同

 

那么如何寻找最长的Ak段呢?

 

先说操作:

我们先寻找到A段中最长的相同前后缀a段(为什么这么做呢?接着往下看吧)

为了直观,将A段分成四份,分别为最长相同前缀后缀a段,a段后第一个位置字符e,和其余部分(略)

 

这时如果判断e==b,那么上面表格中黄色部分,就是最长的相同的前后缀。

 

如果e!= b,那么我们就将a段再分成四份,用相同的方法寻找最长相同前缀后缀,直到a段分无可分,也就是没有任何相同的前后缀,这时j=next[j]=0,a段中只剩下首字母一个元素,再与第i位进行判断,如果还是不相等,那么对不起,配对失败,继续当你的单身狗吧,这时j=next[0]=-1,再次循环时进入到第一个判断,next[i]=0

但是作为一个严谨的小朋友,你可能会问:我现在的确知道a段+e和a段+b是相同的前后缀,那你怎么确定它是最长的相同的前后缀呢?

为了满足这位小朋友的求知欲,接下来证明一下:

我们为了方便起见,把a段+e叫做Ak段(表示从0~k位)

反证法:如果0~k 不是最长的话,势必最长的相同前后缀会包含Ak段(显而易见嘛,我不是最长的前缀,那么最长的前缀一定包含我),假设最长的相同前后缀为Am(0~m位)段

 


观察Am段的组成可以发现,Am段=a段+e+X段(X段的长度未知,并且X段的最后一位等于b,要不然不可能成为最长相同前后缀),Am段除了最后一位字符b,其余部分(因为e的长度为1,Am段除去一个字符b之后的长度,也就是a段+X段的总长度)均属于A段,那么现在Am段在A段中的部分的长度已经大于a段了,这与a段是A段中最长的相同前后缀相矛盾。

 

© 著作权归作者所有

上一篇: 队列
下一篇:
JoshSone
粉丝 7
博文 76
码字总数 32794
作品 0
长春
iOS工程师
私信 提问
加载中

评论(1)

芭比嘟du
芭比嘟du
呱唧呱唧 ✌
KMP 字符串匹配经典算法深度解析

摘要:KMP算法是字符串匹配的经典算法,由于其O(m+n)的时间复杂度,至今仍被广泛应用。大道至简,KMP算法非常简洁,然而,其内部却蕴含着玄妙的理论,以至许多人知其然而不知其所以然。本文旨...

红薯
2011/08/10
2.5K
0
KMP字符串匹配算法

KMP算法,Knuth-Morris-Pratt Algorithm,一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人提出的一种快速模式匹配算法。 KMP朴素算法 原理:子串pattern依次与目标串tar...

长平狐
2013/01/06
198
0
KMP (KMP+拓展KMP)算法总结

KMP及拓展KMP算法 KMP算法是一种线性时间复杂度的字符串匹配算法,它是对BF(Brute-Force,最基本的字符串匹配算法)的改进。对于给定的原始串S和模式串T,需要从字符串S中找到字符串T出现的位...

my_sunshine26
2017/05/28
0
0
数据结构——串的朴素模式和KMP匹配算法

一、朴素模式 假设我们要从主串S=”goodgoogle"中找到子串T=“google"的位置,步骤如下: i表示主串的当前位置下标,j表示子串的当前位置下标,如上图在第一轮比较(i=1开始)中j=4和i=4的位...

lxq_xsyu
2014/12/07
0
0
JavaScript 字符串匹配算法

原文链接 前言 字符串匹配算法,在日常开发中也常被频繁用到。当然,我们可以用正则匹配来完成字符串匹配,但是,学习和理解相关的字符串匹配算法,对于我们技术成长还是有很多好处的。 定义...

Checkson
07/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
357
7
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
11
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部