2019獨角獸企業重金招聘Python工程師標準>>>

一、KMP算法思路啟發2

????? 1.深入探討算法思路

• 這次我們給模式匹配串添加一個K數組（也就是KMP算法中非著名的next數組）；
• 這是一個"智能"的數組，因為他指導著模式匹配串下一步改用第幾號元素去進行匹配。

????? 2.我們接著使用思路啟發1中的案例，再添加next K數組的情況下，再來進行分析

????? (1)思路啟發一

????? 如圖所示，當字符串S與T進行匹配到i5，j5時，發現不匹配，此時第二輪的匹配就不需要回溯到i1，再從j1進行回溯匹配，只需要將匹配串T移動到j1，然后與i5進行匹配，這樣就節省了回溯匹配的時間，提高了效率！

?????

????? 所以，j5對應的k值就為1，即表示匹配串T，下一步移動到j1，重新與串S的上一次匹配的位置進行匹配，即i1與j5進行匹配！

?????

? ? ? 好，我們接著修改，假設原來串S的i4位置不為v而是c，那么就在i4，j4的位置就失配了，所以下一輪就是用j1去，所以k值即為1，依此類推，當j3與i3，j2與i2，j1與i1進行匹配的時候就失配了，則其對應的k值都為1，但是注意當地一個就失配的時候，j1的k值對應的是0，即移到字符串的開頭，如下圖所示：

?????

????? (2)思路啟發二

????? 如圖所示，這個T串與S串的匹配，我們就不能按照前面的思路一了，因為當j3與i3失配時，按照思路一的方式，即把串T移動到j1的位置，然后與串S的i3位置進行匹配了！這樣，我們就錯過了i3與j2的匹配項，因為此時j2與i3是完全匹配的！為什么不能再采用思路一的方法呢，因為在j3失配之前，j1和j2是相等的，那么就需要特殊情況特殊考慮了！

????

????? 按照思路一繼續匹配：

?????

????? 按照思路二繼續匹配，即T從j3移動到j2繼續與i3匹配，即j3的k值為2：

?????

????? 如果匹配串T在j2與i2匹配時就失配，如下圖所示，那么下一輪串T則移動到j1位置繼續與i2進行匹配，那么j2對應的k值為1，j1對應的k值則為0，即移到開頭重新匹配。

?????

????? (3)思路啟發三

????? 如下圖所示，可以看到前面匹配有兩個bb字串，所以當j6與i6失配的時候，i6的前綴為j1，j2，j3即為"bbs"，而j6的后綴為j4，j5，j6即為"bbc"，前綴與后綴匹配的個數有兩個，所以就需要移動T串到j3的位置繼續與串S的i6位置繼續匹配，所以j6的k值為3；

?????

????? 如果串T在j5與i5匹配的時候就失配了，我們可以看到j5后綴就是j3，j4即"sb"，前綴即為j1，j2即"bb"，所以在j5失配時，前綴與后綴匹配的個數只有一個即為"b"，所以，j5失配對應的下一輪匹配位置為2，即j5的k值為2；

?????

????? 由此，我們可以總結出一個規律，當前失配位置的下一輪匹配位置(即k值) = 當前適配位置的前綴和后綴的匹配個數 + 1

????? 然后依此類推，可以很容易直到當在j4，j3，j2，j1失配對應的k值如下圖所示：

?????

????? (4)思路啟發四

????? 通過上面的思路整理，我們看下面這個T串與S串匹配時，當在j5位置失配時，j5的后綴為j2，j3，j4即為"sss"，j5的前綴為j1，j2，j3即為"sss"，所以匹配的個數有3個，根據思路三總結的結論，我們知道j5位置失配對應的下一輪匹配的位置為j4，即k值為4；

?????

????? 依此類推，前面失配時對應的k值如下：

?????

????? 由此，我們可以再回味下"問題是由模式串決定的，而不是由目標串決定的"這句話時，是否就可以真正的體會到其內涵呢？

?

本文為原創文章，如果對你有一點點的幫助，別忘了點贊哦！比心！如需轉載，請注明出處，謝謝！

?

轉載于:https://my.oschina.net/aibinxiao/blog/1850397

總結

以上是生活随笔為你收集整理的数据结构与算法之KMP算法02的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。