Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之KMP算法
概述
從今天開(kāi)始, 小白我將帶大家開(kāi)啟 Java 數(shù)據(jù)結(jié)構(gòu) & 算法的新篇章.
KMP 算法
KMP (Knuth-Morris-Pratt), 是一種改進(jìn)的字符串匹配算法. KMP 算法解決了暴力匹配需要高頻回退的問(wèn)題, KMP 算法在匹配上若干字符后, 字符串位置不需要回退, 從而大大提高效率. 如圖:
舉個(gè)例子 (字符串 “abcabcdef” 匹配字符串 “abcdef”):
次數(shù) | 暴力匹配 | KMP 算法 | 說(shuō)明 |
---|---|---|---|
1 | a bcabcdef a bcdef |
a bcabcdef a bcdef |
a 和 a 匹配 |
2 | ab cabcdef ab cdef |
ab cabcdef ab cdef |
ab 和 ab 匹配 |
3 | abc abcdef abc def |
abc abcdef abc def |
abc 和 abc 匹配 |
4 | abca bcdef abcd ef |
abca bcdef abcd ef |
abca 和 abcd 不匹配, 回退. 暴力匹配回退到索引 1, 即 “b”, KMP 算法索引跳置 3, 即 “a” |
5 | ab cabcdef a bcdef |
abca bcdef a bcdef |
暴力匹配 b 和 a 不匹配, 后移. KMP 算法 a 和 a 匹配 |
6 | abc abcdef a bcdef |
abcab cdef ab cdef |
暴力匹配 c 和 a 不匹配, 后移. KMP 算法 ab 和 ab 匹配 |
7 | abca bcdef a bcdef |
abcabc def abc def |
暴力匹配 a 和 a 匹配. KMP 算法 abc 和 abc 匹配 |
8 | abcab cdef ab cdef |
abcabcd ef abcd ef |
暴力匹配 ab 和 ab 匹配. KMP 算法 abcd 和 abcd 匹配 |
9 | abcabc def abc def |
abcabcde f abcde f |
暴力匹配 abc 和 abc 匹配. KMP 算法 abcde 和 abcde 匹配 |
10 | abcabcd ef abcd ef |
abcabcdef abcdef |
暴力匹配 abcd 和 abcd 匹配. KMP 算法 abcdef 和 abcdef 匹配 , 匹配完成 |
11 | abcabcde f abcde f |
abcabcdef abcdef |
暴力匹配 abcde 和 abcde 匹配. KMP 算法匹配完成 |
12 | abcabcdef abcdef |
abcabcdef abcdef |
暴力匹配 abcd 和 abcd 匹配, 匹配完成. KMP 算法匹配完成 |
部分匹配表
部分匹配表 (Partial Match Table) 指的是 “前綴” 和 “后綴” 的最長(zhǎng)共有元素的長(zhǎng)度.
舉個(gè)例子, 字符串 “ABCDABD” 的前綴與后綴:
字符串 | 前綴 | 后綴 | 共同部分 | 值 |
---|---|---|---|---|
A | NaN | NaN | NaN | 0 |
AB | A | B | NaN | 0 |
ABC | A, AB | C, BC | NaN | 0 |
ABCD | A, AB, ABC | D, CD, BCD | NaN | 0 |
ABCDA | A, AB, ABC, ABCD | A, DA, CDA, BCDA | A | 1 |
ABCDAB | A, AB, ABC, ABCD, ABCDA | B, AB, DAB, CDAB, BCDAB | AB | 2 |
ABCDAB | A, AB, ABC, ABCD, ABCDA, ABCDAB | D, BD, ABD, DABD, CDABD, BCDABD | NaN | 0 |
KMP 算法實(shí)現(xiàn)
重點(diǎn):
KMP 算法中移動(dòng)的位數(shù) = 已匹配的字符數(shù) - 對(duì)應(yīng)的部分匹配值
import java.util.Arrays; public class KMPMatch { public static int Match(String str1, String str2, int[] next) { // 初始化索引 int i = 0; int j = 0; for (; i < str1.length(); i++) { if (j > 0 && str1.charAt(i) != str2.charAt(j)) { // 不匹配, 回退 i = i - next[j - 1]; j = 0; } // 匹配 if (str1.charAt(i) == str2.charAt(j)) { j++; } // 返回索引 if (j == str2.length()) { return i - j + 1; } } return -1; } // 部分匹配 public static int[] getNext(String s) { // 定義數(shù)組 int next[] = new int[s.length()]; // 初始化i, j int i = 0; int j = -1; next[0] = -1; // 遍歷 while (i < s.length() - 1) { if (j == -1 || s.charAt(i) == s.charAt(j)) { // 匹配成功 next[i] = j + 1; i++; j++; } else { //一旦不匹配成功j回退到-1 j = -1; } } return next; } public static void main(String[] args) { // 字符串1 String str1 = "BBCABCDAB ABCDABD"; // 字符串2 String str2 = "ABCDABD"; // 匹配表 int[] next = getNext(str2); System.out.println(Arrays.toString(next)); // KMP算法 int result = Match(str1, str2, next); System.out.println(result); } }
輸出結(jié)果:
[0, 0, 0, 0, 1, 2, 0]
10
到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之KMP算法的文章就介紹到這了,更多相關(guān)Java KMP 算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringBoot整合mybatis/mybatis-plus實(shí)現(xiàn)數(shù)據(jù)持久化的操作
這篇文章主要介紹了SpringBoot整合mybatis/mybatis-plus實(shí)現(xiàn)數(shù)據(jù)持久化,本節(jié)內(nèi)容我們介紹了數(shù)據(jù)持久化的相關(guān)操作,并且是基礎(chǔ)傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)——mysql,需要的朋友可以參考下2022-10-10詳解java操作Redis數(shù)據(jù)庫(kù)的redis工具(RedisUtil,jedis工具JedisUtil,JedisPoo
這篇文章主要介紹了java操作Redis數(shù)據(jù)庫(kù)的redis工具,包括RedisUtil,jedis工具JedisUtil,JedisPoolUtil工具,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),需要的朋友可以參考下2021-08-08java讀取其他服務(wù)接口返回的json數(shù)據(jù)示例代碼
這篇文章主要給大家介紹了關(guān)于java讀取其他服務(wù)接口返回的json數(shù)據(jù)的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2018-03-03Java數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之二叉樹(shù)
今天給大家?guī)?lái)的是關(guān)于Java數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí),文章圍繞著Java二叉樹(shù)展開(kāi),文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下2021-06-06解讀Integer類的parseInt和valueOf的區(qū)別
這篇文章主要介紹了解讀Integer類的parseInt和valueOf的區(qū)別,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-11-11Springboot自定義banner及驗(yàn)證過(guò)程
這篇文章主要介紹了Springboot自定義banner及驗(yàn)證過(guò)程,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04mybatis-plus實(shí)現(xiàn)邏輯刪除的示例代碼
本文主要介紹了mybatis-plus實(shí)現(xiàn)邏輯刪除的示例代碼,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05