Java 資料結構與演算法系列精講之KMP演演算法

2022-02-18 10:00:39

概述

從今天開始, 小白我將帶大家開啟 Java 資料結構 & 演演算法的新篇章.

KMP 演演算法

KMP (Knuth-Morris-Pratt), 是一種改進的字串匹配演演算法. KMP 演演算法解決了暴力匹配需要高頻回退的問題, KMP 演演算法在匹配上若干字元后, 字串位置不需要回退, 從而大大提高效率. 如圖:

舉個例子 (字串「abcabcdef」匹配字串「abcdef」):

次數	暴力匹配	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	abc`a`bcdef abc`d`ef	abc`a`bcdef abc`d`ef	abca 和 abcd 不匹配, 回退. 暴力匹配回退到索引 1, 即「b」, KMP 演演算法索引跳置 3, 即「a」
5	a`b`cabcdef `a`bcdef	abc`a`bcdef `a`bcdef	暴力匹配 b 和 a 不匹配, 後移. KMP 演演算法 a 和 a 匹配
6	ab`c`abcdef `a`bcdef	abc`ab`cdef `ab`cdef	暴力匹配 c 和 a 不匹配, 後移. KMP 演演算法 ab 和 ab 匹配
7	abc`a`bcdef `a`bcdef	abc`abc`def `abc`def	暴力匹配 a 和 a 匹配. KMP 演演算法 abc 和 abc 匹配
8	abc`ab`cdef `ab`cdef	abc`abcd`ef `abcd`ef	暴力匹配 ab 和 ab 匹配. KMP 演演算法 abcd 和 abcd 匹配
9	abc`abc`def `abc`def	abc`abcde`f `abcde`f	暴力匹配 abc 和 abc 匹配. KMP 演演算法 abcde 和 abcde 匹配
10	abc`abcd`ef `abcd`ef	abc`abcdef abcdef`	暴力匹配 abcd 和 abcd 匹配. KMP 演演算法 abcdef 和 abcdef 匹配 , 匹配完成
11	abc`abcde`f `abcde`f	abc`abcdef abcdef`	暴力匹配 abcde 和 abcde 匹配. KMP 演演算法匹配完成
12	abc`abcdef abcdef`	abc`abcdef 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 演演算法實現

重點:

KMP 演演算法中移動的位數 = 已匹配的字元數 - 對應的部分匹配值

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) {

        // 定義陣列
        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);
    }
}

輸出結果:

[0, 0, 0, 0, 1, 2, 0]
10

到此這篇關於Java 資料結構與演算法系列精講之KMP演演算法的文章就介紹到這了,更多相關Java KMP 演演算法內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Java 資料結構與演算法系列精講之KMP演演算法

概述

KMP 演演算法

部分匹配表

KMP 演演算法實現

熱門文章