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