如何通過Java代碼實現(xiàn)KMP算法
更新時間：2019年11月14日 10:59:27 作者：loytime
這篇文章主要介紹了如何通過Java代碼實現(xiàn)KMP算法,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
這篇文章主要介紹了如何通過Java代碼實現(xiàn)KMP算法,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
KMP算法是一種改進的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP算法）。KMP算法的關鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達到快速匹配的目的。具體實現(xiàn)就是實現(xiàn)一個next()函數(shù)，
函數(shù)本身包含了模式串的局部匹配信息。時間復雜度O(m+n)。
代碼如下
import java.util.Arrays;
public class Test {
/**
* @param str 文本串
* @param dest 模式串
* @param next 匹配核心數(shù)組
* @return
*/
public static int kmp(String str, String dest,int[] next) {
for(int i = 0, j = 0; i < str.length(); i++){
if (j > 0 && str.charAt(i) != dest.charAt(j)) {
j = next[j - 1];
}
if (str.charAt(i) == dest.charAt(j)) {
j++;
}
if (j == dest.length()) {
return i-j+1;
}
}
return 0;
}
public static int[] kmpnext(String dest) {
int[] next = new int[dest.length()];
next[0] = 0;
for(int i = 1,j = 0; i < dest.length(); i++) {
if (j > 0 && dest.charAt(j) != dest.charAt(i)) {
j = next[j - 1];
}
if (dest.charAt(i) == dest.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
public static void main(String[] args){
String a = "ABABAE";
String b = "ABABABABAEBEABADAEABAEABABAE";
int[] next = kmpnext(a);
System.out.println(Arrays.toString(next));
int res = kmp(b, a,next);
System.out.println(res);
}
}
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
AsyncConfigurerSupport自定義異步線程池處理異常
這篇文章主要為大家介紹了AsyncConfigurerSupport自定義異步線程池處理異常詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-06-06
Stream 作為 Java 8 的一大亮點，它與 java.io 包里的 InputStream 和 OutputStream 是完全不同的概念。今天通過本文重點給大家介紹java樹結構stream工具類的示例代碼，感興趣的朋友一起看看吧2022-03-03
這篇文章主要介紹了Spring中的@ResponseStatus使用，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要介紹了SpringBoot整合Swagger2代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-03-03
這篇文章主要為大家介紹了SpringBoot整合Apache?Pulsar教程示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-03-03
本文主要介紹了Java中文件寫入內(nèi)容的幾種常見方法,主要包括使用NIO的Files工具類、通過commons-io的FileUtils工具類、RandomAccessFile、PrintWriter和BufferedWriter這幾種,具有一定的參考價值,感興趣的可以了解一下2023-10-10
這篇文章主要介紹了java安全停止線程的方法詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-10-10
IntelliJ IDEA下Maven創(chuàng)建Scala項目的方法步驟
這篇文章主要介紹了IntelliJ IDEA下Maven創(chuàng)建Scala項目的方法步驟，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-06-06
這篇文章主要介紹了java 微信隨機紅包算法的相關資料,并附實例代碼，需要的朋友可以參考下2016-10-10
Java 實戰(zhàn)項目之在線點餐系統(tǒng)的實現(xiàn)流程
讀萬卷書不如行萬里路，只學書上的理論是遠遠不夠的，只有在實戰(zhàn)中才能獲得能力的提升，本篇文章手把手帶你用java+SSM+jsp+mysql+maven實現(xiàn)一個在線點餐系統(tǒng),大家可以在過程中查缺補漏，提升水平2021-11-11