KMP算法中get_next函数分析

原创
2017/05/16 11:45
阅读数 1.2K

看了网上几个号称最简单的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段中最长的相同前后缀相矛盾。

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
呱唧呱唧 ✌
2017/05/16 23:49
回复
举报
更多评论
打赏
1 评论
0 收藏
0
分享
返回顶部
顶部