本文共 1430 字，大约阅读时间需要 4 分钟。
导读：
谈到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 |
转载地址：http://xjtrn.baihongyu.com/