java 實現KMP算法

KMP算法是一種神奇的字符串匹配算法，在對 超長字符串 進行模板匹配的時候比暴力匹配法的效率會高不少。接下來我們從思路入手理解KMP算法。

在對字符串進行匹配的時候我們最容易想到的就是一個個匹配，類似下面這種：

換成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; }

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

以上面gif圖中的兩個字符串

​ txt = “aaacaaab”

​ pat = “aaab”

​ 為例我們來說一下KMP算法的思路。個人能力有限，您可以先行觀看此視頻去簡單學習KMP的基本原理。

簡單原理：構建狀態轉移數組，當遇到無法匹配的字符時根據狀態轉移數組進行回溯，以達到減少遍歷次數的目的。

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

對目標字符串進行遍歷，檢索相同的字符元素。如果遇到不同的字符元素，根據 J（模板字符串的指針）所在的位置依靠狀態轉移數組來回溯遍歷狀態。并在回溯后繼續進行匹配。

import java.util.Arrays;public class KMP { private int[] patArray; // 狀態轉移數組 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) { // 通過匹配模式字符串構建對象 this.pattern = pat; patArray = new int[pattern.length()]; // 創建狀態轉移數組 int j = 0; for (int i = 1; i < pattern.length(); ) { if (pattern.charAt(i) == pattern.charAt(j)){ // 如果i和j指向的字符相同，則將此狀態進行保存patArray[i++] = ++j; // 保存的同時移步下一位 }else {// 如果 i 和 j 指向的字符不相同，則保持i不動，回溯j// 如果回溯后的j指向的字符與i相同，則將此時的狀態進行保存if (j <= pattern.length() - 1 && j >0) { j=patArray[--j]; // 回溯j if (pattern.charAt(i) == pattern.charAt(j)) { // 如果回溯后相同，則保存狀態 patArray[i++] = ++j; }}else if (j == 0) { // 如果回溯到頭，則保存為0狀態 patArray[++i] = 0;} } } } boolean search(String txt){ int j = 0; for (int i = 0; i < txt.length(); i++) { // 對輸入的字符串進行模式匹配 if (txt.charAt(i) != pattern.charAt(j)){// 如果匹配不成功，則根據狀態數組對j進行狀態更改if (j>0)--j; // 回溯j = patArray[j]; }else {++j; // 匹配成功則進入下一個狀態 } if (j == pattern.length()-1){ // 如果成功匹配，返回truereturn true; } } return false;// 匹配不成功 }}

后續的一些思考：

在對比較短的目標字符串而言，毫無疑問使用暴力法的效率（時間復雜度為O（M*N）會快一點，而當目標字符串的長度非常長以后，暴力匹配的效率就會大打折扣。

對于非常長的字符串來說，KMP的O(M+N)的效率相對來說就會非常高。

以上就是java 實現KMP算法的詳細內容，更多關于java 實現KMP算法的資料請關注好吧啦網其它相關文章！