本文章就專講kmp，暴力匹配就不講了（我相信能搜索kmp的，暴力匹配算法應(yīng)該也都了解過了）
為什么網(wǎng)上那么多講kmp 我還發(fā)文章，很多文章我覺得講的不是太通俗易懂，大多數(shù)我看起來都覺得有些懵逼
KMP介紹
提示：以下信息來源百度
KMP算法是一種改進的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特—莫里斯—普拉特操作（簡稱KMP算法）。KMP算法的核心是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達到快速匹配的目的。具體實現(xiàn)就是通過一個next()函數(shù)實現(xiàn)，函數(shù)本身包含了模式串的局部匹配信息。KMP算法的時間復(fù)雜度O(m+n)
上面講了kmp需要求匹配字符串的next數(shù)組來快速匹配，那我們先來講解一下如何求next數(shù)組
一、求Next數(shù)組
求Next數(shù)組前我們需要了解字符串的前綴表與后綴表
前后綴表
如字符串“ABCD”的前后綴表
了解完字符串前后綴，接下來我們要開始求最長公共前后綴
求最長公共前后綴
我們以“aabaac”為例
字符串中要沒有公共的前后綴就為0
從以上方法就能求出字符串“aabaac”的最長公共前后綴數(shù)組為
[0,1,0,1,2,0]
最長相等前后綴表轉(zhuǎn)Next數(shù)組
當然變成Next數(shù)組前還需要進行簡單的處理（其實也就把最長公共前后綴數(shù)組右移而已）
在最長公共前后綴前面加上 -1 并去掉最后一位就是next數(shù)組了
Next數(shù)組的第一位永遠是-1，第二位永遠是0
注意：Next數(shù)組有很多種求法，依據(jù)匹配字符串的代碼來做選擇，我選擇的方法next數(shù)組第一位是-1，還有另一種方法開頭是0，但原理都是相同的所以不必糾結(jié)
二、使用Next數(shù)組來匹配字符串
為了能較好體現(xiàn)kmp算法：
主串：“aaacaacaaad”
模式串：“aaad”
模式串Next數(shù)組：[-1,0,1,2]
在主串和匹配串字符相同的情況下，指針 i 和 j 后移
或者遇到主串和匹配串字符不相同時 但next值為-1時指針 i 和 j 后移
步驟一：
1i、1j、2i、2j代表指針位置及步驟，中間字符相等的地方我就不講了，就主要講重點的地方
指針4i和4j的字符不相同，不匹配位置的next值為2（藍色的a），所以需要將匹配串右移到匹配串索引2的位置
步驟二：
匹配串后移后指針i和j的字符依然還是不相同，不匹配位置的next值為1（藍色的a），所以需要將匹配串右移到匹配串索引1的位置
步驟三：
匹配串后移后指針i和j的字符依然還是不相同，不匹配位置的next值為0（藍色的a），所以需要將匹配串右移到匹配串索引0的位置
步驟四：
匹配串后移后指針i和j的字符依然還是不相同，但這時next值為-1，這就需要指針i和j向后移
步驟五：
指針i和j后移后，（中間字符相同的地方就不解說了），指針到3i和3j的字符不相同，next值為1，然后就和之前講的步驟一樣，需要將匹配串右移到匹配串索引1的位置
步驟六：
后面的步驟就不再多敘述，自己看圖分析
步驟七：
步驟八：
然后這就匹配完成了
文章來源：http://www.zghlxwxcb.cn/news/detail-737478.html
總結(jié)
代碼后續(xù)會補充
非常感謝您能看到這，本人第一次寫文章，所以我可能講的不是很好，如有問題望大家能多多提醒，感謝。下次講sunday算法注：如看不懂，可以的話，麻煩您在評論區(qū)中發(fā)句看不懂，好讓我知道我寫的爛不爛文章來源地址http://www.zghlxwxcb.cn/news/detail-737478.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-串-KMP算法詳解（Next數(shù)組計算）（簡單易懂）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu)] 串與KMP算法詳解](https://imgs.yssmx.com/Uploads/2024/02/825350-1.png)
