KMP算法是要解决的问题是一个字符串中查找指定子串的问题。由于臻臻问我这个问题，所以我不得不再次看看KMP -_-|| ，同时感谢袁涛和王宇晖Orz，（另：默默等待王霸的KMP第三层优化，但愿他能成功）。
先说传统的匹配算法。以图中的字符串为例，第一行是要匹配的目标字符串（称之为主串。其中第i个简写为S[i])，要匹配的字符串称之为子串（也叫模式串，其中第i个简写为P[i]）接下来每行代表一次匹配操作，黄色部分代表匹配成功的部分，红色字符为发现的第一个不匹配的字符。所有字符计数从1开始。所有字符计数从1开始。所有字符计数从1开始。（重要的事情说三遍）
左侧第一列是每一次匹配情况。下面是详细的匹配过程描述。为了方便观察变化，上图中每次移动子串将在新行展现。实际匹配时只在当前行向后移动。
1. 将P[1]和S[1]对齐。
2. 比较S[1]与P[1]是否相同（结果是不相同）。图中第1行
3. 将P[1]和S[2]对齐（把模式串向后移动1个字符的位置）。
4. 比较P[1]与S[2]是否相同（结果是相同）。
5. 比较P[2]与S[3]是否相同（结果是相同）。
6. 比较P[3]与S[4]是否相同（结果是相同）。
7. 比较P[4]与S[5]是否相同（结果是不相同）。图中第2行
8. 将P[1]和S[3]对齐（把模式串向后移动1个字符的位置）。
9. 比较P[1]与S[3]是否相同（结果是不相同）。图中第3行
10. 将P[1]和S[4]对齐（把模式串向后移动1个字符的位置）。
11. 比较P[1]与S[4]是否相同（结果是不相同）。图中第4行
12. 将P[1]和S[5]对齐（把模式串向后移动1个字符的位置）。
13. 比较P[1]与S[5]是否相同（结果是不相同）。图中第5行
14. 将P[1]和S[6]对齐（把模式串向后移动1个字符的位置）。
15. 比较P[1]与S[6]是否相同（结果是相同）。
16. 比较P[2]与S[7]是否相同（结果是相同）。
17. 比较P[3]与S[8]是否相同（结果是相同）。
18. 比较P[4]与S[9]是否相同（结果是相同）。
19. 比较P[5]与S[10]是否相同（结果是相同）。
20. 比较P[6]与S[11]是否相同（结果是相同）。
21. 比较P[7]与S[12]是否相同（结果是相同）。
22. 比较P[8]与S[13]是否相同（结果是不相同）。图中第6行
23. 将P[1]和S[7]对齐（把模式串向后移动1个字符的位置）。
24. 比较P[1]与S[7]是否相同（结果是不相同）。图中第7行
25. 将P[1]和S[8]对齐（把模式串向后移动1个字符的位置）。
26. 比较P[1]与S[8]是否相同（结果是不相同）。图中第8行
27. 将P[1]和S[9]对齐（把模式串向后移动1个字符的位置）。
28. 比较P[1]与S[9]是否相同（结果是相同）。
29. 比较P[2]与S[10]是否相同（结果是相同）。
30. 比较P[3]与S[11]是否相同（结果是相同）。
31. 比较P[4]与S[12]是否相同（结果是相同）。
32. 比较P[5]与S[13]是否相同（结果是不相同）。图中第9行
33. 将P[1]和S[10]对齐（把模式串向后移动1个字符的位置）。
34. 比较P[1]与S[10]是否相同（结果是不相同）。图中第10行
35. 将P[1]和S[11]对齐（把模式串向后移动1个字符的位置）。
36. 比较P[1]与S[11]是否相同（结果是不相同）。图中第11行
37. 将P[1]和S[12]对齐（把模式串向后移动1个字符的位置）。
38. 比较P[1]与S[12]是否相同（结果是相同）。
39. 比较P[2]与S[13]是否相同（结果是不相同）。图中第12行
40. 将P[1]和S[13]对齐（把模式串向后移动1个字符的位置）。
41. 比较P[1]与S[13]是否相同（结果是相同）。
42. 比较P[2]与S[14]是否相同（结果是相同）。
43. 比较P[3]与S[15]是否相同（结果是相同）。
44. 比较P[4]与S[16]是否相同（结果是相同）。
45. 比较P[5]与S[17]是否相同（结果是相同）
46. 比较P[6]与S[18]是否相同（结果是相同）
47. 比较P[7]与S[19]是否相同（结果是相同）
48. 比较P[8]与S[20]是否相同（结果是不相同）图中第13行
49. 将P[1]和S[14]对齐（把模式串向后移动1个字符的位置）。
50. 比较P[1]与S[14]是否相同（结果是不相同）。图中第14行
51. 将P[1]和S[15]对齐（把模式串向后移动1个字符的位置）。
52. 比较P[1]与S[15]是否相同（结果是不相同）。图中第15行
53. 将P[1]和S[16]对齐（把模式串向后移动1个字符的位置）。
54. 比较P[1]与S[16]是否相同（结果是相同）。
55. 比较P[2]与S[17]是否相同（结果是相同）。
56. 比较P[3]与S[18]是否相同（结果是相同）。
57. 比较P[4]与S[19]是否相同（结果是相同）。
58. 比较P[5]与S[20]是否相同（结果是相同）
59. 比较P[6]与S[21]是否相同（结果是相同）
60. 比较P[7]与S[22]是否相同（结果是相同）
61. 比较P[8]与S[23]是否相同（结果是相同）
62. 比较P[9]与S[24]是否相同（结果是相同）
63. 比较P[10]与S[25]是否相同（结果是相同）
64. 匹配成功。图中第16行
仔细观察原始匹配算法的规律，以上述第15步开始为例。
当模式串的前7个字符P[1 2 3 4 5 6 7]与主串S中的某个子部S[6 7 8 9 10 11 12]相匹配时，如果P[8]（图中红色的c）与S[13]（a）匹配失败，下一次将会把P[1]与S[7]对齐，然后从P[1]与S[7]开始向后逐一进行匹配。
也就是说：
当模式串的前i个字符P[1 – i]与主串S中的某个子部S[m ···· m + (i – 1)]相匹配时，如果P[i + 1]（图中红色的c）与S[m + i]（a）匹配失败，下一次将会把P[1]与S[m + 1]对齐，然后从P[1]与S[m + 1]开始向后逐一进行匹配。
至此原始的字符串匹配算法结束。
我们最开始的目的是找到主串S中是否存在子串P，也就是说我们希望尽可能多的匹配子串P的内容。观察图中第6-9行的过程（对应上文步骤14开始的过程）。
当P[8]（图中红色的c）与S[13]（a）匹配失败，会有两次后移子串的操作，这时会发现在第9行中子串P的前4个字符组成的字符串和第6行中前7个字符组成的子串的后4个字符组成的字符串是一样的。也就是图中蓝色框线部分。放到一起来看是这样的：
换句话说，也就是子串前7个字符组成的字符串的头部和尾部有4个字符匹配（下文称之为前缀和后缀）。
这时观察上面的图，那么可以思考一个改进方案，就是当发现P[8]与S[13]不匹配的时候，下一步直接比较P[5]和S[13]（因为前4个已经在图中第6行匹配过了），也就是把子串S移动了3个字符的距离。
在这里我们引入跳转表如下（先不要管怎么算的）。
含义是：当P[j]与主串中某个字符（设为t，在上例中是S[13]）不匹配时，从P[next[j]]（P[5]）开始继续与主串中的t（S[13]）比较（也就是把子串后移j – next[j]个字符的距离），例如上例中的next[8] = 5，含义就是当P[8]与t（S[13]）匹配不成功时，直接从P[5]开始继续与主串中的t（S[13]）比较（也就是把子串后移8-5个字符的距离）。
可以发现，next的数值是和主串无关的，只和这个子串本身有关。那么这样，最原始的匹配步骤就可以变成下面图中的样子。也就是每次尽可能多的匹配子串与主串，不要每次都移动一个进行尝试。
那么问题来了（不是蓝翔），怎么计算next[j]？
根据前面的例子可以看出，next[j]的值就是P[1 ····· j – 1]中可以找到的最长且相等的前缀与后缀的长度再加1（规定第1个值为0，因为如果第一个字母都不匹配的话就要向后移动1个字符的长度，1 = j – next[j] = 1 – 0），比如前面例子中子串前7个字符中可以找到最长且相等的前缀和后缀就是abca，长度是4，所以next[8]的值就是4 + 1 = 5。按照这个原则，就可以构造出上面的跳转表了。
上面的方法是人眼非常方便的做法，但是如果要写程序则会变得非常复杂。并且当字符串变长或者字的数量变多的时候直接查找会变的非常低效。所以需要考虑程序怎么方便快速的实现，在这种时候通常的思路是充分利用之前的结果。
例如想求next[5]，假设next[4]以及以前的next值都已经计算完毕如图。
想求next[5]，也就是模式串前4个字符中能找到最长的一对前后缀长度+1， 这时我们已知next[4] = 1也就是说模式串前3个字符找不到一对前后缀相等，我们尝试考虑加上第4个字符P[4]看看能不能找到，既然已经知道前3个中找不到一对相等的前后缀，那么只需要判断要加入的字符P[4]和P[1]是不是相同，如果相同，那么代表加入P[4]后最长前后缀的长度可以增加1，也就是next[5] = next[4] + 1 = 1 + 1 = 2
另外一个例子
想求next[8]，假设next[7]以及之前的值已知如图。
想求next[8]，也就是模式串前7个字符中能找到最长的一对前后缀长度+1， 这时我们已知next[7] = 4也就是说模式串前6个字符找到最长且相等的一对前后缀长度为3（图中红色和蓝色部分），我们尝试考虑加上第7个字符P[7]看看能不能延长最长前后缀的长度，既然已经知道前6个中找到最且相等的一对前后缀长度为3，那么只需要判断要加入的字符P[7]与P[4]是不是相同（红框后的红圈字符和篮框后的红圈字符），如果相同，那么代表加入P[7]后最长前后缀的长度可以增加1，也就是可以延长也就是next[8] = next[7] + 1 = 4 + 1 = 5
分析上面的过程，其实就是尝试尽可能添加进更多的字符进入已经找到的最长且相等的前后缀中，第一个字符的next值一定是0，从第二个开始使用上面的规律，如果最后一个字符的加入可以延长最长前后缀，那么就加进去，如果之前已经没有最长的前后缀，那么直接写1。
再找一个特殊情况如下（为了说明另一种情况我换了个字符串）。想求next[5]
想求next[5]，也就是模式串前4个字符中能找到最长的一对前后缀长度+1， 这时我们已知next[4] = 2也就是说模式串前3个字符找到最长且相等的一对前后缀长度为1（图中红色和蓝色部分），我们尝试考虑加上第4个字符P[4]看看能不能延长最长前后缀的长度，既然已经知道前3个中找到最且相等的一对前后缀长度为1，那么只需要判断要加入的字符P[4]与P[2]是不是相同（红框后的红圈字符和篮框后的红圈字符），如果相同，那么代表加入P[4]后最长前后缀的长度可以增加1，但是显然P[4]与P[2]不等，加入后无法延长目前最长前后缀的长度。这时候却不能结束，因为你明显能看到前4个字符最长的前后缀长度明明是1，所以要继续尝试将P[4]与P[1]比较，如果相同，那么说明最长前后缀长度可以从0增加到1，所以next[5] = next[2] + 1 = 1 + 1 = 2
说了这么多，求next[j]方法推导总结如下：
next[1] = 0 (j = 1时)
假设next[j] = k，求next[j + 1]。
因next[j] = k (由假设)，所以有：
P[1 ···· (k – 1)] = P[( j – (k – 1)) ···· (j – 2) (j – 1)] (由定义)
分两种情况讨论：
若P[k]=P[j]，则有P[1 ···· (k-1) k] = P[ (j – (k – 1)) (j – (k – 2)) ···· (j -1) j ]，且不存在k’ > k 满足等式
（图中取j = 7的情况）
所以，next[j + 1] = k + 1=next[j] + 1
若P[k] ≠ P[j]( k < j )，则将求next函数值的问题看成一个模式匹配问题，整个模式串既是主串又是模式串。（图中取j=8的情况）
继续设已知next[k] = k’（也就是图中的next[5] = 2）
分两种情况讨论：
若P[k’] = P[j]，则有P[1 2 ···· (k’ – 1) k’] = P[(j – (k’ – 1)) (j – (k’ – 2)) ···· (j – 1) j ] (1 < k’ < k < j )
那么next[j + 1] = k’ + 1 = next[k] + 1
若P[k’] ≠ P[j] ( k < j )，则又将求next函数值的问题看成一个模式匹配问题，整个模式串既是主串又是模式串
重复以上讨论：直至P[j]和模式串中某个字符匹配成功，即找到某个k’’使next[j + 1]=k’’ + 1=next[k’] + 1
反之不存在任何k*(1 < k* < j)，则next[j + 1] = 1。
到此为止，搜索的过程就可以优化成上图的样子了。但是还没完，仔细看，第2次匹配，当发现P[4]（a）与S[5]（b）匹配失败时，下一次匹配按照跳转表应该是P[1]继续和S[5]匹配，但是可以发现P[4]和P[1]是一样的，那么进行两次匹配是没必要的，所以我们就可以再进行一次优化。第9行的情况也同理。
可以简化成下图这样。对应跳转表也在下面。
在第一次的跳转表的基础上，如果发现要跳转的字符和自身相等，那么可以把自身的next值改为要跳转字符的next值，否则保持不变，计算过程中依然充分利用已知的nextval值。举几个例子：
·······
上图中的next[2] = 1，而P[2] ≠ P[1]，所以nextval[2] = next[2] = 1。
·······
上图中的next[4] = 1，而P[4] = P[1]，所以nextval[4] = nextval[1] = 0。
上图中的next[6] = 3，而P[6] = P[3]，所以nextval[6] = nextval[3] = 1。
上图中的next[10] = 2，而P[10] = P[2]，所以nextval[10] = nextval[2] = 1。
经过这两次优化，可以发现，原本需要匹配16次的事情现在只需要匹配6次即可完成。是不是非常神奇？
0 Comments