Java 數(shù)據(jù)結(jié)構與算法系列精講之KMP算法
概述
從今天開始, 小白我將帶大家開啟 Java 數(shù)據(jù)結(jié)構 & 算法的新篇章.
KMP 算法
KMP (Knuth-Morris-Pratt), 是一種改進的字符串匹配算法. KMP 算法解決了暴力匹配需要高頻回退的問題, KMP 算法在匹配上若干字符后, 字符串位置不需要回退, 從而大大提高效率. 如圖:
舉個例子 (字符串 “abcabcdef” 匹配字符串 “abcdef”):
次數(shù) | 暴力匹配 | KMP 算法 | 說明 |
---|---|---|---|
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) 指的是 “前綴” 和 “后綴” 的最長共有元素的長度.
舉個例子, 字符串 “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 算法實現(xiàn)
重點:
KMP 算法中移動的位數(shù) = 已匹配的字符數(shù) - 對應的部分匹配值
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
到此這篇關于Java 數(shù)據(jù)結(jié)構與算法系列精講之KMP算法的文章就介紹到這了,更多相關Java KMP 算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
SpringBoot整合mybatis/mybatis-plus實現(xiàn)數(shù)據(jù)持久化的操作
這篇文章主要介紹了SpringBoot整合mybatis/mybatis-plus實現(xiàn)數(shù)據(jù)持久化,本節(jié)內(nèi)容我們介紹了數(shù)據(jù)持久化的相關操作,并且是基礎傳統(tǒng)的關系型數(shù)據(jù)庫——mysql,需要的朋友可以參考下2022-10-10詳解java操作Redis數(shù)據(jù)庫的redis工具(RedisUtil,jedis工具JedisUtil,JedisPoo
這篇文章主要介紹了java操作Redis數(shù)據(jù)庫的redis工具,包括RedisUtil,jedis工具JedisUtil,JedisPoolUtil工具,本文通過實例代碼給大家介紹的非常詳細,需要的朋友可以參考下2021-08-08java讀取其他服務接口返回的json數(shù)據(jù)示例代碼
這篇文章主要給大家介紹了關于java讀取其他服務接口返回的json數(shù)據(jù)的相關資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧。2018-03-03解讀Integer類的parseInt和valueOf的區(qū)別
這篇文章主要介紹了解讀Integer類的parseInt和valueOf的區(qū)別,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-11-11