KMP算法是一種神奇的字符串匹配算法，在對(duì) 超長(zhǎng)字符串 進(jìn)行模板匹配的時(shí)候比暴力匹配法的效率會(huì)高不少。接下來(lái)我們從思路入手理解KMP算法。

在對(duì)字符串進(jìn)行匹配的時(shí)候我們最容易想到的就是一個(gè)個(gè)匹配，類似下面這種：

換成Java代碼就是：

public static boolean bfSearch(String pattern,String txt){ if (txt.length() < pattern.length()) return false; for (int i = 0; i < txt.length(); i++) { boolean flag = false; for (int j = 0; j < pattern.length(); j++) {if (i+j>=txt.length()) return false;if (txt.charAt(i+j)!=pattern.charAt(j)){ flag = true;} } if (!flag){return true; } } return false; }

暴力匹配算法的時(shí)間復(fù)雜度為O(n*m)，n為模板字符串，m為目標(biāo)字符串，在處理復(fù)雜字符串時(shí)毫無(wú)疑問(wèn)效率會(huì)非常低，由此誕生了KMP算法（時(shí)間復(fù)雜度為O(m+n) )。

以上面gif圖中的兩個(gè)字符串

​ txt = “aaacaaab”

​ pat = “aaab”

​ 為例我們來(lái)說(shuō)一下KMP算法的思路。個(gè)人能力有限，您可以先行觀看此視頻去簡(jiǎn)單學(xué)習(xí)KMP的基本原理。

簡(jiǎn)單原理：構(gòu)建狀態(tài)轉(zhuǎn)移數(shù)組，當(dāng)遇到無(wú)法匹配的字符時(shí)根據(jù)狀態(tài)轉(zhuǎn)移數(shù)組進(jìn)行回溯，以達(dá)到減少遍歷次數(shù)的目的。

1.首先構(gòu)建狀態(tài)轉(zhuǎn)移數(shù)組：

對(duì)匹配模式字符串進(jìn)行遍歷從左向右遍歷，如果 i 和 j（見(jiàn)源碼）所指向的元素相同，則將此狀態(tài)（j所指向的元素位置）進(jìn)行保存最后保存的數(shù)組是一個(gè)Int類型的狀態(tài)碼數(shù)組，每個(gè)元素的含義是回溯時(shí)模板字符串（pattern）的狀態(tài)。

2.構(gòu)建完成后通過(guò)狀態(tài)轉(zhuǎn)移數(shù)組和匹配模式字符串對(duì)傳入的目標(biāo)字符串進(jìn)行匹配。過(guò)程如下：

對(duì)目標(biāo)字符串進(jìn)行遍歷，檢索相同的字符元素。如果遇到不同的字符元素，根據(jù) J（模板字符串的指針）所在的位置依靠狀態(tài)轉(zhuǎn)移數(shù)組來(lái)回溯遍歷狀態(tài)。并在回溯后繼續(xù)進(jìn)行匹配。

3.源碼如下：

import java.util.Arrays;public class KMP { private int[] patArray; // 狀態(tài)轉(zhuǎn)移數(shù)組 private final String pattern;// 匹配模式字符串 public static boolean bfSearch(String pattern,String txt){ if (txt.length() < pattern.length())return false; for (int i = 0; i < txt.length(); i++) { boolean flag = false; for (int j = 0; j < pattern.length(); j++) {if (i+j>=txt.length())return false;if (txt.charAt(i+j)!=pattern.charAt(j)){ flag = true;} } if (!flag){return true; } } return false; } KMP(String pat) { // 通過(guò)匹配模式字符串構(gòu)建對(duì)象 this.pattern = pat; patArray = new int[pattern.length()]; // 創(chuàng)建狀態(tài)轉(zhuǎn)移數(shù)組 int j = 0; for (int i = 1; i < pattern.length(); ) { if (pattern.charAt(i) == pattern.charAt(j)){ // 如果i和j指向的字符相同，則將此狀態(tài)進(jìn)行保存patArray[i++] = ++j; // 保存的同時(shí)移步下一位 }else {// 如果 i 和 j 指向的字符不相同，則保持i不動(dòng)，回溯j// 如果回溯后的j指向的字符與i相同，則將此時(shí)的狀態(tài)進(jìn)行保存if (j <= pattern.length() - 1 && j >0) { j=patArray[--j]; // 回溯j if (pattern.charAt(i) == pattern.charAt(j)) { // 如果回溯后相同，則保存狀態(tài) patArray[i++] = ++j; }}else if (j == 0) { // 如果回溯到頭，則保存為0狀態(tài) patArray[++i] = 0;} } } } boolean search(String txt){ int j = 0; for (int i = 0; i < txt.length(); i++) { // 對(duì)輸入的字符串進(jìn)行模式匹配 if (txt.charAt(i) != pattern.charAt(j)){// 如果匹配不成功，則根據(jù)狀態(tài)數(shù)組對(duì)j進(jìn)行狀態(tài)更改if (j>0)--j; // 回溯j = patArray[j]; }else {++j; // 匹配成功則進(jìn)入下一個(gè)狀態(tài) } if (j == pattern.length()-1){ // 如果成功匹配，返回truereturn true; } } return false;// 匹配不成功 }}

后續(xù)的一些思考：

在對(duì)比較短的目標(biāo)字符串而言，毫無(wú)疑問(wèn)使用暴力法的效率（時(shí)間復(fù)雜度為O（M*N）會(huì)快一點(diǎn)，而當(dāng)目標(biāo)字符串的長(zhǎng)度非常長(zhǎng)以后，暴力匹配的效率就會(huì)大打折扣。

對(duì)于非常長(zhǎng)的字符串來(lái)說(shuō)，KMP的O(M+N)的效率相對(duì)來(lái)說(shuō)就會(huì)非常高。

以上就是java 實(shí)現(xiàn)KMP算法的詳細(xì)內(nèi)容，更多關(guān)于java 實(shí)現(xiàn)KMP算法的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！