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