欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之KMP算法

 更新時(shí)間:2022年02月18日 09:15:58   作者:我是小白呀  
在很多地方也都經(jīng)??吹街v解KMP算法的文章,看久了好像也知道是怎么一回事,但總感覺(jué)有些地方自己還是沒(méi)有完全懂明白。這兩天花了點(diǎn)時(shí)間總結(jié)一下,有點(diǎn)小體會(huì),我希望可以通過(guò)我自己的語(yǔ)言來(lái)把這個(gè)算法的一些細(xì)節(jié)梳理清楚,也算是考驗(yàn)一下自己有真正理解這個(gè)算法

概述

從今天開(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 abcabcdef abcdef abcabcdef abcdef a 和 a 匹配
2 abcabcdef abcdef abcabcdef abcdef ab 和 ab 匹配
3 abcabcdef abcdef abcabcdef abcdef abc 和 abc 匹配
4 abcabcdef abcdef abcabcdef abcdef abca 和 abcd 不匹配, 回退. 暴力匹配回退到索引 1, 即 “b”, KMP 算法索引跳置 3, 即 “a”
5 abcabcdef abcdef abcabcdef abcdef 暴力匹配 b 和 a 不匹配, 后移. KMP 算法 a 和 a 匹配
6 abcabcdef abcdef abcabcdef abcdef 暴力匹配 c 和 a 不匹配, 后移. KMP 算法 ab 和 ab 匹配
7 abcabcdef abcdef abcabcdef abcdef 暴力匹配 a 和 a 匹配. KMP 算法 abc 和 abc 匹配
8 abcabcdef abcdef abcabcdef abcdef 暴力匹配 ab 和 ab 匹配. KMP 算法 abcd 和 abcd 匹配
9 abcabcdef abcdef abcabcdef abcdef 暴力匹配 abc 和 abc 匹配. KMP 算法 abcde 和 abcde 匹配
10 abcabcdef abcdef abcabcdef abcdef 暴力匹配 abcd 和 abcd 匹配. KMP 算法 abcdef 和 abcdef 匹配 , 匹配完成
11 abcabcdef abcdef 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ù)持久化的操作

    這篇文章主要介紹了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,JedisPoolUtil)

    詳解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-08
  • java讀取其他服務(wù)接口返回的json數(shù)據(jù)示例代碼

    java讀取其他服務(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-03
  • Java數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之二叉樹(shù)

    Java數(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ū)別

    這篇文章主要介紹了解讀Integer類的parseInt和valueOf的區(qū)別,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-11-11
  • Springboot自定義banner及驗(yàn)證過(guò)程

    Springboot自定義banner及驗(yàn)證過(guò)程

    這篇文章主要介紹了Springboot自定義banner及驗(yàn)證過(guò)程,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-04-04
  • 基于RecyclerChart的KLine繪制詳解

    基于RecyclerChart的KLine繪制詳解

    這篇文章主要為大家詳細(xì)介紹了基于RecyclerChart實(shí)現(xiàn)KLine繪制的相關(guān)資料,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2023-03-03
  • Java實(shí)現(xiàn)猜字小游戲

    Java實(shí)現(xiàn)猜字小游戲

    這篇文章給大家分享小編隨手寫(xiě)的猜字小游戲,基于java代碼寫(xiě)的,感興趣的朋友跟隨小編一起看看吧
    2019-11-11
  • Java中的封裝、繼承和多態(tài),你真的都懂了嗎

    Java中的封裝、繼承和多態(tài),你真的都懂了嗎

    Java中的封裝、繼承和多態(tài)知識(shí)點(diǎn)是學(xué)習(xí)java必備的基礎(chǔ)知識(shí),看似簡(jiǎn)單,真正理解起來(lái)還是有一定難度的,今天小編再次通過(guò)實(shí)例代碼給大家講解java 封裝繼承多態(tài)知識(shí),感興趣的朋友一起學(xué)習(xí)下吧
    2021-05-05
  • mybatis-plus實(shí)現(xiàn)邏輯刪除的示例代碼

    mybatis-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

最新評(píng)論