如何通過Java代碼實(shí)現(xiàn)KMP算法
這篇文章主要介紹了如何通過Java代碼實(shí)現(xiàn)KMP算法,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)，因此人們稱它為克努特——莫里斯——普拉特操作（簡(jiǎ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);
}
}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
SpringBoot中添加監(jiān)聽器及創(chuàng)建線程的代碼示例
這篇文章主要介紹了SpringBoot中如何添加監(jiān)聽器及創(chuàng)建線程，文中有詳細(xì)的代碼示例，具有一定的參考價(jià)值,需要的朋友可以參考下2023-06-06
Spring相關(guān)知識(shí)點(diǎn)的總結(jié)與梳理
今天小編就為大家分享一篇關(guān)于Spring相關(guān)知識(shí)點(diǎn)的總結(jié)與梳理，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-02-02
Java 數(shù)據(jù)流之Broadcast State
這篇文章主要介紹了Java 數(shù)據(jù)流之Broadcast State，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
Java實(shí)現(xiàn)貪吃蛇游戲(1小時(shí)學(xué)會(huì))
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)貪吃蛇游戲，1小時(shí)學(xué)會(huì)貪吃蛇游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05
Java 字符數(shù)組轉(zhuǎn)字符串的常用方法
文章總結(jié)了在Java中將字符數(shù)組轉(zhuǎn)換為字符串的幾種常用方法,包括使用String構(gòu)造函數(shù)、String.valueOf()方法、StringBuilder以及Arrays.toString()方法,每種方法都有其適用的場(chǎng)景和性能特點(diǎn),感興趣的朋友跟隨小編一起看看吧2025-01-01
使用Nacos實(shí)現(xiàn)動(dòng)態(tài)路由的步驟和代碼示例
這篇文章主要介紹了使用 Nacos 實(shí)現(xiàn) Spring Cloud Gateway 的動(dòng)態(tài)路由,本文給大家介紹了具體的實(shí)現(xiàn)步驟和代碼案例,感興趣的小伙伴跟著小編一起來看看吧2024-09-09
Java實(shí)現(xiàn)折半插入排序算法的示例代碼
折半插入排序（Binary Insertion Sort）是對(duì)插入排序算法的一種改進(jìn)。不斷的依次將元素插入前面已排好序的序列中。本文將利用Java語言實(shí)現(xiàn)這一排序算法，需要的可以參考一下2022-08-08
java Executors工具類的相關(guān)方法使用創(chuàng)建
這篇文章主要為大家介紹了java Executors工具類的相關(guān)方法使用創(chuàng)建，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-11-11
SpringBoot?2.5.5整合輕量級(jí)的分布式日志標(biāo)記追蹤神器TLog的詳細(xì)過程
分布式追蹤系統(tǒng)是一個(gè)最終的解決方案，如果您的公司已經(jīng)上了分布式追蹤系統(tǒng)，這篇文章主要介紹了SpringBoot?2.5.5整合輕量級(jí)的分布式日志標(biāo)記追蹤神器TLog,需要的朋友可以參考下2022-10-10
Java實(shí)現(xiàn)調(diào)用對(duì)方http接口得到返回?cái)?shù)據(jù)
這篇文章主要介紹了Java實(shí)現(xiàn)調(diào)用對(duì)方http接口得到返回?cái)?shù)據(jù)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09