[KMP]一行代码助你快速理解KMP算法
今天被张棒棒老师邀请在数据结构课堂上分享一下我对KMP算法的心得，为了防止课堂时间短大家听得不是很明白，我写了一份说明文档如下，也上传到这里和大家分享一下。觉得ok的点一下赞哦哈哈哈
第一部分
书中（P82）KMP算法框架如下：
这个框架相对来说是比较容易理解的，但是next函数值的求法确实KMP算法的核心，书上（P83）求解next的代码如下：
个人感觉这是比较难理解的，但是严奶奶的代码又好又妙经历过时间的考验。不过至于怎么理解上面的代码还是看大家的，我这里只介绍一种通过找规律的很简单的方式可以快速口答得到next函数值，这种方法的使用可以完成：（1）校验自己的代码是否正确；（2）加深对KMP算法的理解。
通过通读P82和P83可以发现KMP算法中next具有如下三条性质（实际上是四条，有一条比较隐秘用于特殊情况的处理）：
性质I：
性质II:若，则有
；
性质III:若，则有
,且
。
第二部分
那么在这里我们就可以使用一条编程语句把上面三个性质统一表达出来：
其中。
看起来是有一些长，但是使用起来是非常有规律的，下面我们以课本上的例子进行检验：
要计算字符串‘abaabcac’的移动数组next[],下面计算j=3时即字符‘a’所对应的next[3],应用公式如下：
因为P[1]≠P[2]，所以执行的是next[3]=(next[1]+1)=1,即有
继续计算j=4时即字符‘a’所对应的next[4]，应用公式如下：
因为P[3]=P[1]，所以执行的是next[4]=next[3]+1=2,即有
同理因为P[4]≠P[2],所以执行的是next[5]=next[2]+1=2
j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
P[j] |
a |
b |
a |
a |
b |
c |
a |
c |
next[j] |
0 |
1 |
1 |
2 |
2 |
|
|
|
同理因为P[5]=P[2],所以执行的是next[6]=next[5]+1=3
j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
P[j] |
a |
b |
a |
a |
b |
c |
a |
c |
next[j] |
0 |
1 |
1 |
2 |
2 |
3 |
|
|
第三部分
接下来如果继续按照上面的思路，将是
因为P[6]≠P[3]，所以next[7]=next[3]+1=2和课本上的答案不符。怎么回事呢，难道是我们的公式错了吗？没错。。还真是公式错了，但是这里出现的一个问题是很轻易用自然语言表达清楚但是不容易修改公式的地方（不然我们完全可以用上面的一行代码代替书本上的几行代码）。
怎么解释呢？
我们回忆一下KMP算法为什么要计算next[j],是为了更高速的匹配，为了尽可能得到最大的步长（这样会比单个字符移动速度快很多）。看表格我们可以发现一个问题：
P[3]=P1[]，这非常有趣，这表明P[3]和P[1]是等价的，其实如果你仍旧按照我们最初的公式进行计算对于KMP算法来说是完全没问题的，但是这不是最标准的next函数值（因为中间会多进行移位）。
虽然正巧碰到P[3]=P[1]的机会不多，但是为了得到标准的next函数值，我们最好明白这个特殊情况，虽然也不难。
第四部分
那么接着进行计算
因为P[6]≠P[1]，所以next[7]=next[1]+1=1
j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
P[j] |
a |
b |
a |
a |
b |
c |
a |
c |
next[j] |
0 |
1 |
1 |
2 |
2 |
3 |
1 |
|
接着继续，
因为P[7]=P[1]，所以next[8]=next[7]+1=2.
j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
P[j] |
a |
b |
a |
a |
b |
c |
a |
c |
next[j] |
0 |
1 |
1 |
2 |
2 |
3 |
1 |
2 |