這篇文章來說說如何簡單理解KMP，BM算法。之前看過一些文章說，KMP算法很難理解。 可我并不覺得。 我反而覺得它容易理解。平時我們寫java代碼的時候， 判斷一個字符串是否存在包含另一個字符串都是直接 string.contains(str)， 可你知道它是實(shí)現(xiàn)的么？ 不妨親自去看看它是如何實(shí)現(xiàn)的？

看此文章之前，嚴(yán)重建議先去看看阮一峰老師寫的的KMP算法文章。如果那篇文章都可以完全理解了，那么就沒必要看這篇文章浪費(fèi)時間了。

字符串匹配在平時開發(fā)中還是很常用的，只不過我們一般都是調(diào)用jdk提供的方法直接使用。

下面以這個為例子，來描述KMP算法原理。

在字符串"BBCABCDABABCDABCDABDE"，判斷里面是否包含另一個字符串"ABCDABD"？

在字符串匹配算法中，我們除了可以逐一匹配之外，別無它法。包括KMP，BM算法也是逐一匹配的，只不過是KMP，BM算法用了很多討巧的方式提高了匹配效率。

首先先來看看暴力匹配，暴力匹配就是逐一匹配，當(dāng)匹配失敗后，子串往后移動一個字符。主串中的“B”，與子串中的“A”不匹配，子串往后移動一個字符

然后繼續(xù)往后匹配。匹配失敗就往后一個字符。

當(dāng)子串中的前6個字符匹配上了，但最后一個字符匹配失敗，子串又只能往后移動一個字符，有點(diǎn)可惜。

一直到主串中的“ABCDABD”與子串完全匹配，那么就匹配成功。

這種暴力匹配的效率太低了，因為不管你前面匹配成功時，到后面字符一旦匹配失敗時，那么前面匹配的成功的，又得重新匹配一遍。

下面我們來假設(shè)一種情況(當(dāng)然這種假設(shè)情況是錯誤的)，只要匹配失敗，那么移動我們匹配上的字符數(shù)量，看看會發(fā)現(xiàn)什么情況？

舉例：子串“ABCDABD”，當(dāng)匹配到“ABCD”完成時，匹配“A”失敗，那么后面移動4個字符。匹配失敗，移動一個字符子串匹配到后一個“D”時，匹配失敗，移動6個字符

根據(jù)前面的假設(shè)，字符所有的字符都匹配過了，那么就可以移動6個字符。根據(jù)上圖移動6個字符之后的效果

匹配失敗，移動一個字符。

當(dāng)子串匹配到后一個“D”時，又匹配失敗，往后移動6個字符。最后錯過想要匹配的字符串。

這種假設(shè)，有個很明顯的問題，就是尺度大了。錯過了我們想要匹配的字符串。

其實(shí)我們思路已經(jīng)對了一半了，這時應(yīng)該反思錯在哪了？

以這種情況為例， 按照假設(shè)就是直接移動6個字符。但是子串前綴“AB”是在后面有出現(xiàn)的。

正確的話，是應(yīng)該移動到后面的AB那里，繼續(xù)開始匹配。根據(jù)上圖匹配失敗之后，正確的移動字符數(shù)

是的。KMP算法就是可以按照這種思路理解的。一般情況下，當(dāng)已經(jīng)匹配過子串中，前面的子串中的字符串在后續(xù)沒有出現(xiàn)，那么就可以移動所有匹配過的字符串。

如果前面的子串中的字符串在后續(xù)中有出現(xiàn)，那么移動到字符出現(xiàn)到后續(xù)出現(xiàn)那里。

再舉個例子。

ABCDABDCA 這個子串中，當(dāng)匹配到第2個“A”失敗時，子串前面匹配過的“ABCD”的前綴和前中綴，都不會在中后綴，后綴中出現(xiàn)，那么就可以直接移動4個字符。

ABCDABDCA 這個子串中，當(dāng)匹配到第2個“D”失敗時，子串前面匹配過的“ABCDAB”的前綴，“AB”是后綴中出現(xiàn)了，那么就只能移到“AB”那里了，即 6 - 2 = 4，移動4個字符。

簡單理解就是： 先把匹配過的字符直接移動過去，看看會不會錯過什么。 如果不會，那么就確認(rèn)移動。 如果會，那么回退到目標(biāo)位置。

根據(jù)KMP算法的部分匹配值，可以計算出目標(biāo)位置的值。

由于阮一峰老師關(guān)于部分匹配值和KMP算法總結(jié)太棒了，所以有關(guān)部分匹配值的概念，怎么計算，就參考阮一峰老師文章吧。

最后來說說，java里面， String.contains方法實(shí)現(xiàn)。

java中的String.contains也是使用暴力匹配的方式，沒有使用KMP，BM之類的算法。

至于為什么，這個就發(fā)散一下，留給自己思考吧。

最后的最后，既然提到了KMP算法，另一個也很常用，且一般情況下效率更高的BM算法，就留給你自己看吧，興許下一篇文章就是說說BM算法。

以上， good night.

總結(jié)

以上是生活随笔為你收集整理的字符串匹配算法Java_如何简单理解字符串匹配算法？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。