Java數(shù)據(jù)結構之KMP算法的實現(xiàn)

更新時間：2022年11月19日 08:18:25 作者：秋落雨微涼

這篇文章主要為大家詳細介紹了Java數(shù)據(jù)結構中KMP算法的原理與實現(xiàn)，文中的示例代碼講解詳細，對我們學習Java有一定的幫助，需要的可以參考一下

問題介紹

首先我們先介紹適用于KMP算法的問題：

給定一個字符串S，以及一個模式串P,所有字符串中只包含大小寫英文字母以及阿拉伯數(shù)字。
模式串P在字符串S中多次作為子串出現(xiàn)。
求出模式串P在字符串S中所有出現(xiàn)的位置的起始下標。

我們給出一個問題的簡單示例：

// 輸入 p長度 p s長度 s
3
aba
5
ababa
    
// 輸出結果
0 2

暴力求解

所有問題我們都是在暴力求解的基礎上進行更新迭代的，所以我們首先給出暴力求解：

// 下面為偽代碼，只是起到思路作用

// 首先我們需要創(chuàng)造s[],p[]，并賦值
S[N],P[N]
    
// 然后我們開始匹配，我們會從S的第一個字符開始匹配，設置一個flag判斷該字符開始的字符串是否與P字符匹配
// 該算法從每個i開始，全部進行匹配
for(int i = 1;i <= n;i++ ){
    boolean flag = true;
    for(int j = 1;j <= m;j++){
        if(s[i+j-1] != p[j]){
            flag = false;
            break;
        }
    }
}

// 我們給出一套完整的暴力求解方法

/**

 * 暴力破解法

 * @param ts 主串

 * @param ps 模式串

 * @return 如果找到，返回在主串中第一個字符出現(xiàn)的下標，否則為-1

 */

public static int bf(String ts, String ps) {

    char[] t = ts.toCharArray();

    char[] p = ps.toCharArray();

    int i = 0; // 主串的位置

    int j = 0; // 模式串的位置

    while (i < t.length && j < p.length) {

       if (t[i] == p[j]) { 
           
           // 當兩個字符相同，就比較下一個
           i++;
           j++;

       } else {

           i = i - j + 1; // 一旦不匹配，i后退（從之前i的下一位開始，也是遍歷所有i）

           j = 0; // j歸0
       }
    }

    // 當上面循環(huán)結束，必定是i到頭或者j到頭，如果是j到頭，則說明存在子串符合父串，我們就將頭位置i返回
    if (j == p.length) {
       return i - j;
    } else {
       return -1;
    }

}

// 但是我們會發(fā)現(xiàn)：我們可以不讓i回退而是讓j回退，使j回退到能夠與當前i相匹配的點位，然后繼續(xù)進行主串和模式串的匹配

首先我們會發(fā)現(xiàn)這個算法的時間復雜度為O(n^2)

我們其中可以優(yōu)化的點就是i的位置更新，我們可以根據(jù)p字符串的特性來判斷i在失敗后最近可以移動到哪個點位！

知識補充

我們?yōu)榱藢W習KMP算法，我們需要補充一些下面會用到的知識：

s[ ]是模式串，即比較長的字符串。
p[ ]是模板串，即比較短的字符串。（這樣可能不嚴謹。。。）
“非平凡前綴”：指除了最后一個字符以外，一個字符串的全部頭部組合。
“非平凡后綴”：指除了第一個字符以外，一個字符串的全部尾部組合。（后面會有例子，均簡稱為前/后綴）
“部分匹配值”：前綴和后綴的最長共有元素的長度。
next[ ]是“部分匹配值表”，即next數(shù)組，它存儲的是每一個下標對應的“部分匹配值”，是KMP算法的核心。（后面作詳細講解）。

我們所用到的思想是：

在每次失配時，不是把p串往后移一位，而是把p串往后移動至下一次可以和前面部分匹配的位置，這樣就可以跳過大多數(shù)的失配步驟
而每次p串移動的步數(shù)就是通過查找next[ ]數(shù)組確定的

Next示例

我們給出一個簡單的Next示例：

// 首先我們給出一個next手寫實例

/*
模板串為：ABABAA
    
next[0]代表t[0]-t[0]，即"A" , "A"的前綴和后綴都為空集，共有元素的長度為0.

next[1]代表t[0]-t[1]，即"AB"，前綴為“A”，后綴為“B”,共有元素的長度為0..

next[2]代表t[0]~t[2]，即"ABA"，前綴為“AB"，后綴為"BA"，最大前后綴即"A",長度為1.

next[3]代表t[0]~t[3]，即"ABAB"，前綴為"ABA"后綴為"BAB”,最大前后綴即"AB ",長度為2.

next[4]代表t[0]~t[4]，即"ABABA",前綴為"ABAB"，后綴為"BABA",最大前后綴即" ABA",長度為3.

next[5]代表t[0]-t[5]，即" ABABAA",前綴為“ABABA",T后綴為“BABAA";最大前后綴即"A",長度為1.

*/

// 我們next的作用是使next[j]=k使 P[0 ~ k-1] == P[j-k ~ j-1]、
// 當?shù)趎個數(shù)不匹配時，我們讓j回退到k，這時我們的主串和模式串的前綴還屬于匹配狀態(tài)，我們繼續(xù)進行匹配
例如 ababc
    我們如果匹配到c不符合時，我們可以使j回退到k（這里的k是2，即a）再繼續(xù)進行匹配
    因為我們的c前面的ab和開頭的ab是匹配的，我們主串中的i前面肯定也是ab，我們的l前面也是ab，所以兩者匹配，我們可以繼續(xù)后面的匹配
    相當于我們的x不變，我們將j放在2的位置，前面的ab已完成匹配，我們只需要匹配abc即可

// 公式書寫就是下述：
    
當T[i] != P[j]時

有T[i-j ~ i-1] == P[0 ~ j-1]

由P[0 ~ k-1] == P[j-k ~ j-1]

必然：T[i-k ~ i-1] == P[0 ~ k-1]

Next代碼

我們給出求解Next的代碼展示：

public static int[] getNext(String ps) {

    char[] p = ps.toCharArray();

    int[] next = new int[p.length];

    // 這里的next[0]需要等于-1
    // 因為j在最左邊時，不可能再移動j了，這時候要應該是i指針后移。所以在代碼中才會有next[0] = -1;這個初始化。
    next[0] = -1;

    // 這里設置j的初始值從第一個開始（我們需要得到全部next數(shù)組）
    int j = 0;

    // 這里設置k，k就是應該返回的位置，也就是我們常說的前綴和后綴匹配區(qū)域的前綴的后一個位置
    int k = -1;

    // 進行循環(huán)，得到next數(shù)組
    while (j < p.length - 1) {

        // 首先是k==-1時，說明前面已無匹配狀態(tài)，我們重新開始
        // 然后是p[j] == p[k]，說明循環(huán)時新添加的值，與我們應該返回比對的位置相同
        // 同時由于我們之前的部分都是已經匹配成功的，所以加上這個數(shù)使我們的匹配長度又增加一位
       if (k == -1 || p[j] == p[k]) {

           // 當兩個字符相等時要跳過（因為p[k]與S[i]不符合的話，由于我們的p[j]=p[k]，所以肯定也不符合，我們直接跳下一步）
           if (p[++j] == p[++k]) { 

              next[j] = next[k];

           } else {
			// 因為在P[j]之前已經有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）
			// 這時候現(xiàn)有P[k] == P[j]，我們是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。
       		// 即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1
            // 前面我們已經進行了j++和k++，所以這里直接賦值即可
              next[j] = k;

           }

       } else {
		// 如果當前狀態(tài)無法匹配，我們就跳回上一個前綴后綴相同部分再來判斷是否前后綴相同
           k = next[k];

       }

    }

    return next;

}

匹配示例

我們給出簡單的匹配示例：

匹配相對而言就比較簡單了

主串：abababc

模式串：abc

我們首先進行i++，j++范圍的匹配，當?shù)谌?，即a和c匹配不成功時，我們不移動i，而是移動j

我們將j=2,移動到j=0,即next[2]的位置，在之后一直匹配并再對j進行一次移動，到最后匹配成功為止

匹配代碼

我們給出對應的匹配代碼：

/*該代碼實際上是由暴力求解代碼改造過來的*/

public static int KMP(String ts, String ps) {

    char[] t = ts.toCharArray();

    char[] p = ps.toCharArray();

    int i = 0; // 主串的位置

    int j = 0; // 模式串的位置

    int[] next = getNext(ps);
    
    // 開始判斷（設置邊界值）
    while (i < t.length && j < p.length) {

        // 當j為-1時，要移動的是i，當然j也要歸0
        // 如果匹配成功，兩者都進行移動，開始下一位比對
       if (j == -1 || t[i] == p[j]) { 

           i++;

           j++;

       } else {
		   // 如果比對失敗，我們將 j 返回next數(shù)組指定位置繼續(xù)匹配
           
           // i不需要回溯了
           // i = i - j + 1;

           j = next[j]; // j回到指定位置

       }

    }

    // 最后同樣進行判斷，是否符合條件
    if (j == p.length) {

       return i - j;

    } else {

       return -1;

    }

}

完整代碼

最后為大家展示一下完整代碼：

import java.util.Scanner;

class ppp {

    /**
     * 主代碼
     * @param args
     */
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        String ts = scanner.nextLine();

        String ps = scanner.nextLine();

        int kmp = KMP(ts, ps);

        System.out.println(kmp);
    }

    /**
     * kmp算法
     * @param ts
     * @param ps
     * @return
     */
    public static int KMP(String ts, String ps) {

        char[] t = ts.toCharArray();

        char[] p = ps.toCharArray();

        int i = 0; // 主串的位置

        int j = 0; // 模式串的位置

        int[] next = getNext(ps);

        // 開始判斷（設置邊界值）
        while (i < t.length && j < p.length) {

            // 當j為-1時，要移動的是i，當然j也要歸0
            // 如果匹配成功，兩者都進行移動，開始下一位比對
            if (j == -1 || t[i] == p[j]) {

                i++;

                j++;

            } else {
                // 如果比對失敗，我們將 j 返回next數(shù)組指定位置繼續(xù)匹配

                // i不需要回溯了
                // i = i - j + 1;

                j = next[j]; // j回到指定位置

            }

        }

        // 最后同樣進行判斷，是否符合條件
        if (j == p.length) {

            return i - j;

        } else {

            return -1;

        }

    }

    /**
     * next數(shù)組求解
     * @param ps
     * @return
     */
    public static int[] getNext(String ps) {

        char[] p = ps.toCharArray();

        int[] next = new int[p.length];

        // 這里的next[0]需要等于-1
        // 因為j在最左邊時，不可能再移動j了，這時候要應該是i指針后移。所以在代碼中才會有next[0] = -1;這個初始化。
        next[0] = -1;

        // 這里設置j的初始值從第一個開始（我們需要得到全部next數(shù)組）
        int j = 0;

        // 這里設置k，k就是應該返回的位置，也就是我們常說的前綴和后綴匹配區(qū)域的前綴的后一個位置
        int k = -1;

        // 進行循環(huán)，得到next數(shù)組
        while (j < p.length - 1) {

            // 首先是k==-1時，說明前面已無匹配狀態(tài)，我們重新開始
            // 然后是p[j] == p[k]，說明循環(huán)時新添加的值，與我們應該返回比對的位置相同
            // 同時由于我們之前的部分都是已經匹配成功的，所以加上這個數(shù)使我們的匹配長度又增加一位
            if (k == -1 || p[j] == p[k]) {

                // 當兩個字符相等時要跳過
                //（因為p[k]與S[i]不符合的話，由于我們的p[j]=p[k]，所以肯定也不符合，我們直接跳下一步）
                if (p[++j] == p[++k]) {

                    next[j] = next[k];

                } else {
                    // 因為在P[j]之前已經有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）
                    // 這時候現(xiàn)有P[k] == P[j]，我們是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。
                    // 即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1
                    // 前面我們已經進行了j++和k++，所以這里直接賦值即可
                    next[j] = k;

                }

            } else {
                // 如果當前狀態(tài)無法匹配，我們就跳回上一個前綴后綴相同部分再來判斷是否前后綴相同
                k = next[k];

            }

        }

        return next;

    }
}

以上就是Java數(shù)據(jù)結構之KMP算法的實現(xiàn)的詳細內容，更多關于Java KMP算法的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: