Java怎么實現KMP算法

本篇內容主要講解“Java怎么實現KMP算法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java怎么實現KMP算法”吧!

KMP 算法

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

舉個例子 (字符串 “abcabcdef” 匹配字符串 “abcdef”):

部分匹配表

部分匹配表 (Partial Match Table) 指的是 “前綴” 和 “后綴” 的最長共有元素的長度.

舉個例子, 字符串 “ABCDABD” 的前綴與后綴:

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算法”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！