算法笔记(一):浅谈next数组原理

导读:

       谈到next字符串匹配,自然就想到kmp字符串匹配算法,可以说next数组是kmp算法中的一种,当然小编觉得next比较简单首先写下来。


 一、next数组是什么

       next数组的理解之前,你要明白什么是kmp算法,kmp算法又称D.E.Knuth,J.H.Morris和V.R.Pratt(克努特——莫里斯——普拉特)算法,就是三个发现这个算法的三个前沿程序员的名字,是不是很厉害!相信我们未来也可以o(* ̄▽ ̄*)ブ。好了,废话不多说。首先我们都知道kmp是一个字符串匹配算法,而字符串的本质又是一个数组,所以next数组的匹配自然相关。那么next数组是怎么一个匹配的呢?让我们看看。

 

                      下面有一组数:ababaaababaa(随便出的)

 第一步:画表

                  现在,我们先画一个next数组表

next数组
匹配的数据  a b a b a a a b a b a a
    序号 1 2 3 4 5 6 7 8 9 10 11 12
    next                        

                然后闭着眼睛把前面的a和b的next值写上0和1先。咦,为什么要闭着眼睛呢?因为是规定的!规定!!!凡事都应该有规定,就连算法也是一样的。

next数组
匹配的数据  a b a b a a a b a b a a
    序号 1 2 3 4 5 6 7 8 9 10 11 12
    next 0 1                    

第二步:匹配

                其实原理超级简单,现在我们可以看到第三位的数为a,那么第三位的a的前一位b的next值是不是1?然后b的next1的对应的序号1是不是第一位的a?a和b相等吗?不相等。那么a的next值前面还有值吗?有继续匹配,没有则输出next+1。下面做两方面的解释,为了防止不会的情况发生,从哪里理解都是理解。


                                                     任务:匹配第三位的a值

方案一理解:

                         第三位的a前面 ——>b的next值对应的序号的数据是否和b相等?——>是,则输出匹配相等的值下面next值+1;否,则继续根据next值往前寻找是否和b相匹配相等的值,输出next+1

方案二理解:

           算法笔记(一):浅谈next数组原理

next数组
匹配的数据  a b a b a a a b a b a a
    序号 1 2 3 4 5 6 7 8 9 10 11 12
    next 0 1 1                  

 


                                             任务:匹配第四位的b值

              

                                  算法笔记(一):浅谈next数组原理

            所以第四位的b值就是第三位成功匹配的a下面的next值+1,就是2

next数组
匹配的数据  a b a b a a a b a b a a
    序号 1 2 3 4 5 6 7 8 9 10 11 12
    next 0 1 1 2                

 

            由于前一位的匹配第一次就匹配成功了和匹配第四位b值操作一致,下面不一一举例,下面是多次往前找匹配成功的例子。


                                             任务:匹配第七位的b值

                                算法笔记(一):浅谈next数组原理

                   找到第七位前面的值对应的next值,然后一直根据next值往前根据序号一直找,直到和要匹配的数值前一位数匹配即可。

next数组
匹配的数据  a b a b a a a b a b a a
    序号 1 2 3 4 5 6 7 8 9 10 11 12
    next 0 1 1 2 3 4 2          

                   是不是很简单?!bingo!就是这么简单,剩下的不说也相信你们跃跃欲试了。下面的空也相当简单,大家可以填完在看下答案。

 

 

 

 


      谢谢大家的观看~比心❤

 

 

 

 

答案:

next数组
匹配的数据  a b a b a a a b a b a a
    序号 1 2 3 4 5 6 7 8 9 10 11 12
    next 0 1 1 2 3 4 2 2

3

4 5 6