算法笔记(一):浅谈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数组表
匹配的数据 | 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先。咦,为什么要闭着眼睛呢?因为是规定的!规定!!!凡事都应该有规定,就连算法也是一样的。
匹配的数据 | 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
方案二理解:
匹配的数据 | 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值
所以第四位的b值就是第三位成功匹配的a下面的next值+1,就是2
匹配的数据 | 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值往前根据序号一直找,直到和要匹配的数值前一位数匹配即可。
匹配的数据 | 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!就是这么简单,剩下的不说也相信你们跃跃欲试了。下面的空也相当简单,大家可以填完在看下答案。
谢谢大家的观看~比心❤
答案:
匹配的数据 | 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 |