java 實現(xiàn)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的基本原理。
簡單原理：構建狀態(tài)轉移數(shù)組，當遇到無法匹配的字符時根據狀態(tài)轉移數(shù)組進行回溯，以達到減少遍歷次數(shù)的目的。
1.首先構建狀態(tài)轉移數(shù)組：
對匹配模式字符串進行遍歷
從左向右遍歷，如果 i 和 j（見源碼）所指向的元素相同，則將此狀態(tài)（j所指向的元素位置）進行保存
最后保存的數(shù)組是一個Int類型的狀態(tài)碼數(shù)組，每個元素的含義是回溯時模板字符串（pattern）的狀態(tài)。
2.構建完成后通過狀態(tài)轉移數(shù)組和匹配模式字符串對傳入的目標字符串進行匹配。過程如下：
對目標字符串進行遍歷，檢索相同的字符元素。
如果遇到不同的字符元素，根據 J（模板字符串的指針）所在的位置依靠狀態(tài)轉移數(shù)組來回溯遍歷狀態(tài)。并在回溯后繼續(xù)進行匹配。
3.源碼如下：
import java.util.Arrays;
public class KMP {
private int[] patArray; // 狀態(tài)轉移數(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) { // 通過匹配模式字符串構建對象
this.pattern = pat;
patArray = new int[pattern.length()]; // 創(chuàng)建狀態(tài)轉移數(shù)組
int j = 0;
for (int i = 1; i < pattern.length(); ) {
if (pattern.charAt(i) == pattern.charAt(j)){
// 如果i和j指向的字符相同，則將此狀態(tài)進行保存
patArray[i++] = ++j; // 保存的同時移步下一位
}else {
// 如果 i 和 j 指向的字符不相同，則保持i不動，回溯j
// 如果回溯后的j指向的字符與i相同，則將此時的狀態(tài)進行保存
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++) {
// 對輸入的字符串進行模式匹配
if (txt.charAt(i) != pattern.charAt(j)){
// 如果匹配不成功，則根據狀態(tài)數(shù)組對j進行狀態(tài)更改
if (j>0)--j; // 回溯
j = patArray[j];
}else {
++j; // 匹配成功則進入下一個狀態(tài)
}
if (j == pattern.length()-1){ // 如果成功匹配，返回true
return true;
}
}
return false;// 匹配不成功
}
}
后續(xù)的一些思考：
在對比較短的目標字符串而言，毫無疑問使用暴力法的效率（時間復雜度為O（M*N）會快一點，而當目標字符串的長度非常長以后，暴力匹配的效率就會大打折扣。
對于非常長的字符串來說，KMP的O(M+N)的效率相對來說就會非常高。
以上就是java 實現(xiàn)KMP算法的詳細內容，更多關于java 實現(xiàn)KMP算法的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了Java中Servlet3.0異步處理的原理以及遇到的問題分析，需要的朋友參考一下。2017-12-12
詳解Java的Hibernate框架中的set映射集與SortedSet映射
這篇文章主要介紹了詳解Java的Hibernate框架中的set映射集與SortedSet映射,Hibernate是Java的SSH三大web開發(fā)框架之一,需要的朋友可以參考下2015-12-12
這篇文章主要介紹了MyBatis如何通過攔截修改SQL問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
mybatis spring配置SqlSessionTemplate的使用方式
這篇文章主要介紹了mybatis spring配置SqlSessionTemplate的使用方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
Spring JDK動態(tài)代理實現(xiàn)過程詳解
這篇文章主要介紹了Spring JDK動態(tài)代理實現(xiàn)過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-02-02
DDD（Domain-Driven Design 領域驅動設計）是由Eric Evans最先提出，目的是對軟件所涉及到的領域進行建模，以應對系統(tǒng)規(guī)模過大時引起的軟件復雜性的問題2021-06-06
本文主要介紹了Java接口測試之日志框架Logback的具體使用，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
這篇本文主要對Java中synchronized鎖進行深入理解，文中通過synchronized的優(yōu)化，synchronized的實現(xiàn)原理及synchronized的升級過程來介紹Java中synchronized鎖，感興趣的同學可以跟著小編一起來學習2023-05-05
Sentinel 是一個開源的高可用性、高擴展性的實時流量控制框架,它可以用于保護服務穩(wěn)定性,防止系統(tǒng)因為流量過大而崩潰,這篇文章我們所介紹的是滑動窗口,它是 Sentinel 實現(xiàn)限流和降級的重要組件之一,感興趣的同學跟著小編來看看吧2023-09-09
這篇文章主要介紹了JAVA如何轉換樹結構數(shù)據代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-03-03