1.kmp算法基本介紹

• KMP 是一個解決模式串在文本串是否出現(xiàn)過，如果出現(xiàn)過，最早出現(xiàn)的位置的經(jīng)典算法。
• Knuth-Morris-Pratt 字符串查找算法，簡稱為 “KMP 算法”，常用于在一個文本串 S 內(nèi)查找一個模式串 P 的出現(xiàn)位置，這個算法由Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年聯(lián)合發(fā)表，故取這 3 人的姓氏命名此算法。
• KMP 方法算法就利用之前判斷過的信息，通過一個 next 數(shù)組，保存模式串中前后最長公共子序列的長度，每次回溯時，通過 next 數(shù)組找到，前面匹配過的位置，省去了大量的計算時間。

2.字符串的最長公共前后綴&部分匹配表

2.1 什么是最長公共前后綴

1?? 字符串的前綴是指不包含最后一個字符的所有以第一個字符（索引為0）開頭的連續(xù)子串

比如字符串 “ABABA” 的前綴有：A，AB，ABA，ABAB

2?? 字符串的后綴是指不包含第一個字符的所有以最后一個字符結(jié)尾的連續(xù)子串

比如字符串 “ABABA” 的后綴有：BABA，ABA，BA，A

3?? 公共前后綴：一個字符串的 所有前綴連續(xù)子串 和 所有后綴連續(xù)子串 中相等的子串

比如字符串 “ABABA”

• 前綴有：A，AB，ABA，ABAB
• 后綴有：BABA，ABA，BA，A

因此公共前后綴有：A ，ABA

4?? 最長公共前后綴：所有公共前后綴 的 長度最長的 那個子串

比如字符串 “ABABA” ，公共前后綴有：A ，ABA

由于 ABA 是 三個字符長度，A 是一個字符長度，那么最長公共前后綴就是 ABA

?? 再比如說一個字符串 str = “ABCABD”

• 對于str從 索引為0 開始的子串 “A” 而言：

  1. 前綴：不包含最后一個字符A的 所有以第一個字符A開頭 的 連續(xù)子串 不存在
  2. 后綴：不包含第一個字符A 的 所有以最后一個字符A結(jié)尾 的 連續(xù)子串 不存在

  因此該子串的最長公共前后綴 為 0

• 對于str從 索引為0 開始的子串 “AB” 而言：

  1. 前綴：不包含 最后一個字符B 的 所有以第一個字符A開頭 的 連續(xù)子串 有 —— “A”
  2. 后綴：不包含 第一個字符A 的 所有以最后一個字符B結(jié)尾 的 連續(xù)子串 有 —— “B”

  因此該子串的最長公共前后綴 為 0

• 對于str從 索引為0 開始的子串 “ABC” 而言：

  1. 前綴：不包含 最后一個字符C 的 所有以第一個字符A開頭 的 連續(xù)子串 有 —— “A”，“AB”
  2. 后綴：不包含 第一個字符A 的 所有以最后一個字符C 結(jié)尾 的 連續(xù)子串有 —— “BC”，“C”

  前綴與后綴的連續(xù)子串不存在相同的，因此該子串的最長公共前后綴 為 0

• 對于str從 索引為0 開始的子串 “ABCA” 而言：

  1. 前綴：不包含 最后一個字符A 的 所有以第一個字符A開頭 的 連續(xù)子串 有 —— “A”，“AB”，“ABC”
  2. 后綴：不包含 第一個字符A 的 所有以最后一個字符A 結(jié)尾 的 連續(xù)子串有 —— “BCA”，“CA”，“A”

  前綴與后綴的連續(xù)子串中存在相同且最長的子串 A，因此該子串的最長公共前后綴 為 1

• 對于str從 索引為0 開始的子串 “ABCAB” 而言：

  1. 前綴：不包含 最后一個字符B 的 所有以第一個字符A開頭 的 連續(xù)子串 有 —— “A”，“AB”，“ABC”，“ABCA”
  2. 后綴：不包含 第一個字符A 的 所有以最后一個字符B 結(jié)尾 的 連續(xù)子串有 —— “BCAB”，“CAB”，“AB”，“B”

  前綴與后綴的連續(xù)子串中存在相同且最長的子串 AB，因此該子串的最長公共前后綴 為 2

• 對于str從 索引為0 開始的子串 “ABCABD” 而言：

  1. 前綴：不包含 最后一個字符D 的 所有以第一個字符A開頭 的 連續(xù)子串 有 —— “A”，“AB”，“ABC”，“ABCA”，“ABCAB”
  2. 后綴：不包含 第一個字符A 的 所有以最后一個字符D 結(jié)尾 的 連續(xù)子串有 —— “BCABD”，“CABD”，“ABD”，“BD”，“D”

  前綴與后綴的連續(xù)子串不存在相同的，因此該子串的最長公共前后綴 為 0

2.2 什么是部分匹配表Next

個人理解：對于字符串str，從 第一個字符開始的每個子串 的 最后一個字符 與 該子串的最長公共前后綴的長度 的對應(yīng)關(guān)系表格。這個表我們以 int[] next 數(shù)組方式進行存儲。

比如說上面舉的例子：

• 子串 “A”：最后一個字符是 A，該子串的最長公共前后綴長度是 0，因此對應(yīng)關(guān)系就是 A - 0
• 子串 “AB”：最后一個字符是 B，該子串的最長公共前后綴長度是 0，因此對應(yīng)關(guān)系就是 B - 0
• 子串 “ABC”：最后一個字符是 C，該子串的最長公共前后綴長度是 0，因此對應(yīng)關(guān)系就是 C - 0
• 子串 “ABCA”：最后一個字符是 A，該子串的最長公共前后綴長度是 1，因此對應(yīng)關(guān)系就是 A - 1
• 子串 “ABCAB”：最后一個字符是 B，該子串的最長公共前后綴長度是 2，因此對應(yīng)關(guān)系就是 B - 2
• 子串 “ABCABD”：最后一個字符是 D，該子串的最長公共前后綴長度是 0，因此對應(yīng)關(guān)系就是 D - 0

因此綜上，我們說該字符串 str 的部分匹配表為：

那么對應(yīng)的next數(shù)組就是 int[] next = {0, 0, 0, 1, 2, 0}

2.3 字符串最長公共前后綴&部分匹配表的代碼實現(xiàn)

下面的代碼可以參考圖中實例進行分析：

    /**
     * 獲取一個字符串 pattern 的部分匹配表
     *
     * @param patternStr 用于模式匹配字符串
     * @return 存儲部分匹配表的每個子串的最長公共前后綴的 next數(shù)組
     */
    public static int[] kmpNext(String patternStr) {
        //將 patternStr 轉(zhuǎn)為 字符數(shù)組形式
        char[] patternArr = patternStr.toCharArray();

        //預(yù)先創(chuàng)建一個next數(shù)組，用于存儲部分匹配表的每個子串的最長公共前后綴
        int[] next = new int[patternStr.length()];

        /*
            從第一個字符（對應(yīng)索引為0）開始的子串，如果子串的長度為1，那么肯定最長公共前后綴為0
            因為這唯一的一個字符既是第一個字符，又是最后一個字符，所以前后綴都不存在 -> 最長公共前后綴為0
         */
        next[0] = 0;

        /*
          len有兩個作用：
            1. 用于記錄當(dāng)前子串的最長公共前后綴長度
            2. 同時知道當(dāng)前子串的最長公共前后綴的前綴字符串對應(yīng)索引 [0,len-1]/當(dāng)前子串最長公共前綴字符串的下一個字符的索引  <-- 可以拿示例分析一下
         */
        int len = 0;

        //從第二個字符開始遍歷，求索引在 [0,i] 的子串的最長公共前后綴長度
        int i = 1;
        while (i < patternArr.length) {
            /*
                1.已經(jīng)知道了上一個子串 對應(yīng)索引[0,i-1] 的最長公共前后綴長度為 len
                  的前綴字符串是 索引[0,len-1]，對應(yīng)相等的后綴字符串是 索引[i-len,i-1]

                2.因此我們可以以 上一個子串的最長公共前后綴字符串 作為拼接參考
                  比較一下 patternArr[len] 與 patternArr[i] 是否相等
             */
            if (patternArr[len] == patternArr[i]) {
                /*
                    1.如果相等即 patternArr[len]==patternArr[i]，
                      那么就可以確定當(dāng)前子串的最長公共前后綴的
                      前綴字符串是 索引[0,len] ，對應(yīng)相等的后綴字符串是 索引[i-len,i]

                    2.由于是拼接操作，那么當(dāng)前子串的最長公共前后綴長度只需要在上一個子串的最長公共前后綴長度的基礎(chǔ)上 +1 即可
                      即 next[i] = next[i-1] + 1 ，

                    3.由于 len 是記錄的子串的最長公共前后綴長度，對于當(dāng)前我們所在的代碼位置而言
                      len 還是記錄的上一個子串的最長公共前后綴長度，因此：
                      next[i] = next[i-1] + 1 等價于 next[i] = ++len
                 */

                // 等價于 next[i] = next[i-1] + 1
                next[i] = ++len;
                //既然找到了索引在[0,i]的子串的最長公共前后綴字符串長度，那就 i+1 去判斷以下一個字符結(jié)尾的子串的最長公共前后綴長度
                i++;
            }else {
                /*
                    1.如果不相等 patternArr[len]!=patternArr[i]
                      我們想要求當(dāng)前子串 對應(yīng)索引[0,i] 的最長公共前后綴長度
                      我們就不能以 上一個子串的最長公共前后綴：前綴字符串pre  后綴字符串post （毫無疑問pre==post） 作為拼接參考

                    2.但可以思考一下：
                      pre的最長公共前綴字符串： 索引 [      0        , next[len-1] )
                      是等于
                      post的最長公共后綴字符串：索引 [ i-next[len-1] ,     i       )

                      則我們 就以 pre的最長公共前綴字符串/post的最長公共后綴字符串 作為拼接參考
                      去判斷 pre的最長公共前綴字符串的下一個字符patternArr[next[len-1]] 是否等于 post的最長公共后綴字符串的下一個字符patternArr[i]

                    3.在第 1,2 步分析的基礎(chǔ)上
                      我們可以在判斷出 patternArr[len]!=patternArr[i] 后，
                      不去執(zhí)行第二步：patternArr[next[len-1]] 是否等于 patternArr[i]，
                      可以先修改len的值：len = next[len-1]，len就成了 pre的最長公共前綴字符串長度/post的最長公共后綴字符串長度，
                      修改完之后，再去判斷下一個字符 是否相等，即 判斷 patternArr[len] 是否等于 patternArr[i]
                      仔細觀察，這不又是在判斷 這個循環(huán)中 if-else 語句嗎

                    4.關(guān)于 len 這個值，在循環(huán)開始時我們解釋的是：上一個子串的最長公共前后綴字符串的長度
                      但實際上我們在這里改為 len = next[len-1] 表示上一個子串的最長公共前后綴字符串的最長公共前后綴字符串的長度
                      是沒有問題的，等價于上一個子串的較小的公共前后綴字符串。
                      既然進入了 else 語句說明字符不相等，就不能以 上一個子串的最長公共前后綴字符串 作為 拼接參考，就應(yīng)當(dāng)去縮小參考范圍。
                 */
                if(len==0) {

                    /*
                        len為0說明上一個子串已經(jīng)沒有了公共前后綴字符串
                        則我們沒有繼續(xù)尋找的必要 --> 索引在[0, i]的當(dāng)前子串的最長公共前后綴字符串長度就是0
                     */
                    next[i] = len;

                    //繼續(xù)尋找下一個字符串的最長公共前后綴字符串長度
                    i++;

                }else{
                    len = next[len - 1];
                }

            }
        }

        return next;
    }

2.4 代碼測試

package kmp;

import java.util.Arrays;

/**
 * @author 狐貍半面添
 * @create 2022-11-22 22:43
 */
public class KMPAlgorithm {
    public static void main(String[] args) {
        String patternStr = "ABCDABD";
		//輸出結(jié)果：[0, 0, 0, 0, 1, 2, 0]
        System.out.println(Arrays.toString(kmpNext(str2)));
    }

    /**
     * 獲取一個字符串 pattern 的部分匹配表
     *
     * @param patternStr 用于模式匹配字符串
     * @return 存儲部分匹配表的每個子串的最長公共前后綴的 next數(shù)組
     */
    public static int[] kmpNext(String patternStr) {
        //將 patternStr 轉(zhuǎn)為 字符數(shù)組形式
        char[] patternArr = patternStr.toCharArray();

        //預(yù)先創(chuàng)建一個next數(shù)組，用于存儲部分匹配表的每個子串的最長公共前后綴
        int[] next = new int[patternStr.length()];

        /*
            從第一個字符（對應(yīng)索引為0）開始的子串，如果子串的長度為1，那么肯定最長公共前后綴為0
            因為這唯一的一個字符既是第一個字符，又是最后一個字符，所以前后綴都不存在 -> 最長公共前后綴為0
         */
        next[0] = 0;

        /*
          len有兩個作用：
            1. 用于記錄當(dāng)前子串的最長公共前后綴長度
            2. 同時知道當(dāng)前子串的最長公共前后綴的前綴字符串對應(yīng)索引 [0,len-1]/當(dāng)前子串最長公共前綴字符串的下一個字符的索引  <-- 可以拿示例分析一下
         */
        int len = 0;

        //從第二個字符開始遍歷，求索引在 [0,i] 的子串的最長公共前后綴長度
        int i = 1;
        while (i < patternArr.length) {
            /*
                1.已經(jīng)知道了上一個子串 對應(yīng)索引[0,i-1] 的最長公共前后綴長度為 len
                  的前綴字符串是 索引[0,len-1]，對應(yīng)相等的后綴字符串是 索引[i-len,i-1]

                2.因此我們可以以 上一個子串的最長公共前后綴字符串 作為拼接參考
                  比較一下 patternArr[len] 與 patternArr[i] 是否相等
             */
            if (patternArr[len] == patternArr[i]) {
                /*
                    1.如果相等即 patternArr[len]==patternArr[i]，
                      那么就可以確定當(dāng)前子串的最長公共前后綴的
                      前綴字符串是 索引[0,len] ，對應(yīng)相等的后綴字符串是 索引[i-len,i]

                    2.由于是拼接操作，那么當(dāng)前子串的最長公共前后綴長度只需要在上一個子串的最長公共前后綴長度的基礎(chǔ)上 +1 即可
                      即 next[i] = next[i-1] + 1 ，

                    3.由于 len 是記錄的子串的最長公共前后綴長度，對于當(dāng)前我們所在的代碼位置而言
                      len 還是記錄的上一個子串的最長公共前后綴長度，因此：
                      next[i] = next[i-1] + 1 等價于 next[i] = ++len
                 */

                // 等價于 next[i] = next[i-1] + 1
                next[i] = ++len;
                //既然找到了索引在[0,i]的子串的最長公共前后綴字符串長度，那就 i+1 去判斷以下一個字符結(jié)尾的子串的最長公共前后綴長度
                i++;
            }else {
                /*
                    1.如果不相等 patternArr[len]!=patternArr[i]
                      我們想要求當(dāng)前子串 對應(yīng)索引[0,i] 的最長公共前后綴長度
                      我們就不能以 上一個子串的最長公共前后綴：前綴字符串pre  后綴字符串post （毫無疑問pre==post） 作為拼接參考

                    2.但可以思考一下：
                      pre的最長公共前綴字符串： 索引 [      0        , next[len-1] )
                      是等于
                      post的最長公共后綴字符串：索引 [ i-next[len-1] ,     i       )

                      則我們 就以 pre的最長公共前綴字符串/post的最長公共后綴字符串 作為拼接參考
                      去判斷 pre的最長公共前綴字符串的下一個字符patternArr[next[len-1]] 是否等于 post的最長公共后綴字符串的下一個字符patternArr[i]

                    3.在第 1,2 步分析的基礎(chǔ)上
                      我們可以在判斷出 patternArr[len]!=patternArr[i] 后，
                      不去執(zhí)行第二步：patternArr[next[len-1]] 是否等于 patternArr[i]，
                      可以先修改len的值：len = next[len-1]，len就成了 pre的最長公共前綴字符串長度/post的最長公共后綴字符串長度，
                      修改完之后，再去判斷下一個字符 是否相等，即 判斷 patternArr[len] 是否等于 patternArr[i]
                      仔細觀察，這不又是在判斷 這個循環(huán)中 if-else 語句嗎

                    4.關(guān)于 len 這個值，在循環(huán)開始時我們解釋的是：上一個子串的最長公共前后綴字符串的長度
                      但實際上我們在這里改為 len = next[len-1] 表示上一個子串的最長公共前后綴字符串的最長公共前后綴字符串的長度
                      是沒有問題的，等價于上一個子串的較小的公共前后綴字符串。
                      既然進入了 else 語句說明字符不相等，就不能以 上一個子串的最長公共前后綴字符串 作為 拼接參考，就應(yīng)當(dāng)去縮小參考范圍。
                 */
                if(len==0) {

                    /*
                        len為0說明上一個子串已經(jīng)沒有了公共前后綴字符串
                        則我們沒有繼續(xù)尋找的必要 --> 索引在[0, i]的當(dāng)前子串的最長公共前后綴字符串長度就是0
                     */
                    next[i] = len;

                    //繼續(xù)尋找下一個字符串的最長公共前后綴字符串長度
                    i++;

                }else{
                    len = next[len - 1];
                }

            }
        }

        return next;
    }
}

3.根據(jù)部分匹配表搜索字符串匹配位置

3.1 匹配成功一個就退出匹配的代碼

3.1.1 KMP算法的大致步驟

1. 求出模式字符串patternStr的部分匹配表，已知待匹配的字符串 matchStr

2. 定義兩個指針 i 和 j，分別指向 patternStr 和 matchStr ，初始化為0

3. 判斷 patternStr[i] 和 matchStr[j] 是否相等

   • 如果相等，則繼續(xù)向后匹配：i++, j++

   • 如果不相等，則 i 不變，調(diào)整 j 為 模式字符串pattern? 的 上一個子串（索引 [ 0, j-1 ]）的最長公共前綴字符串的下一個索引位置，該索引位置也是最長公共前綴/后綴字符串的長度：j = next[ j - 1 ]

     解釋一下不相等為什么要這樣做：

     1?? 在不相等的時候，我們可以知道前面已經(jīng)匹配的字符串 str1 和 str2 肯定是完全相等的

     • str1：在 matchStr 中對應(yīng)索引 [ i - j , i - 1 ]
     • str2：在 patternStr 中對應(yīng)索引 [ 0 , j - 1 ]

     2?? 由于 完全相等，則 str1 的 最長公共后綴字符串 一定等于 str2 的 最長公共前綴字符串，那么：

     • 將 i 定位到 str1 的 最長公共后綴字符串 的 下一個字符位置，但很明顯，i 此時的位置肯定已經(jīng)是在 str1 的最長公共后綴字符串的下一個字符的位置，因此 i 的值不需要做調(diào)整
     • 將 j 定位到 str2 的 最長公共前綴字符串 的 下一個字符位置 ，next [ j - 1] 不僅代表 上一個子串str1的最長公共前后綴字符串長度，也是最長公共前綴字符串的下一個字符的索引。因此，我們只需要：j = next[ j - 1 ]

     3?? 修改完畢，我們此時已經(jīng)匹配的字符串：

     • 在 matchStr 中 對應(yīng)索引 [ i - j , i - 1 ]
     • 在 patternStr 中 對應(yīng)索引 [ 0 , j - 1 ]

     4?? 那么我們再繼續(xù)比較已經(jīng)匹配的字符串后面的字符就可以了，即 判斷 patternStr[i] 和 matchStr[j] 是否相等，這又回到了 步驟三?。?！

     

4. 判斷 i 和 j 是否超出 各自的最大索引值

   • 如果都沒到超出 各自最大索引值，就繼續(xù)執(zhí)行第三步進行比較（說明是個循環(huán)）
   • 如果至少有一個超出了 各自最大索引值，就退出循環(huán)

5. 循環(huán)結(jié)束后，判斷 j 是否超出了 模式字符串的最大索引值文章來源地址http://www.zghlxwxcb.cn/news/detail-729277.html

   • 如果超出了，說明匹配成功，返回 patternStr 字符串匹配到的 matchStr 的第一個字符串的起始索引位置：i - j
   • 如果沒有超出，說明匹配失敗，返回 -1 表示沒有匹配到

3.1.2 代碼實現(xiàn)+測試

package kmp;

import java.util.Arrays;

/**
 * @author 狐貍半面添
 * @create 2022-11-22 22:43
 */
public class KMPAlgorithm {
    public static void main(String[] args) {
        String matchStr = "AABABADDABAC";
        String patternStr = "ABA";

        // 輸出：index = 1
        System.out.println("index = " + kmpSearch(matchStr, patternStr, kmpNext(patternStr)));

    }

    /**
     * kmp搜索算法
     *
     * @param matchStr   原字符串
     * @param patternStr 子串
     * @param next       子串對應(yīng)的部分匹配表
     * @return 如果是-1，就是沒有匹配到，否則就返回第一個匹配的位置
     */
    public static int kmpSearch(String matchStr, String patternStr, int[] next) {

        int i = 0, j = 0;

        while (i < matchStr.length() && j < patternStr.length()) {

            if (matchStr.charAt(i) == patternStr.charAt(j)) {
                //相等就繼續(xù)進行匹配
                i++;
                j++;

            } else {
                //如果 patternStr[i] 和 matchStr[j] 不相等

                if (j == 0) {
                    /*
                        表示 matchStr 沒有匹配到 patternStr的第一個字符
                        那直接將 matchStr 的指針 i 向后移動一位即可
                     */
                    i++;
                } else {
                    j = next[j - 1];
                }
            }

        }
        return j == patternStr.length() ? i - j : -1;
    }

    /**
     * 獲取一個字符串 pattern 的部分匹配表
     *
     * @param patternStr 用于模式匹配字符串
     * @return 存儲部分匹配表的每個子串的最長公共前后綴的 next數(shù)組
     */
    public static int[] kmpNext(String patternStr) {
        //將 patternStr 轉(zhuǎn)為 字符數(shù)組形式
        char[] patternArr = patternStr.toCharArray();

        //預(yù)先創(chuàng)建一個next數(shù)組，用于存儲部分匹配表的每個子串的最長公共前后綴
        int[] next = new int[patternStr.length()];

        /*
            從第一個字符（對應(yīng)索引為0）開始的子串，如果子串的長度為1，那么肯定最長公共前后綴為0
            因為這唯一的一個字符既是第一個字符，又是最后一個字符，所以前后綴都不存在 -> 最長公共前后綴為0
         */
        next[0] = 0;

        /*
          len有兩個作用：
            1. 用于記錄當(dāng)前子串的最長公共前后綴長度
            2. 同時知道當(dāng)前子串的最長公共前后綴的前綴字符串對應(yīng)索引 [0,len-1]  <-- 可以拿示例分析一下
         */
        int len = 0;

        //從第二個字符開始遍歷，求索引在 [0,i] 的子串的最長公共前后綴長度
        int i = 1;
        while (i < patternArr.length) {
            /*
                1.已經(jīng)知道了上一個子串 對應(yīng)索引[0,i-1] 的最長公共前后綴長度為 len
                  的前綴字符串是 索引[0,len-1]，對應(yīng)相等的后綴字符串是 索引[i-len,i-1]

                2.因此我們可以以 上一個子串的最長公共前后綴字符串 作為拼接參考
                  比較一下 patternArr[len] 與 patternArr[i] 是否相等
             */
            if (patternArr[len] == patternArr[i]) {
                /*
                    1.如果相等即 patternArr[len]==patternArr[i]，
                      那么就可以確定當(dāng)前子串的最長公共前后綴的
                      前綴字符串是 索引[0,len] ，對應(yīng)相等的后綴字符串是 索引[i-len,i]

                    2.由于是拼接操作，那么當(dāng)前子串的最長公共前后綴長度只需要在上一個子串的最長公共前后綴長度的基礎(chǔ)上 +1 即可
                      即 next[i] = next[i-1] + 1 ，

                    3.由于 len 是記錄的子串的最長公共前后綴長度，對于當(dāng)前我們所在的代碼位置而言
                      len 還是記錄的上一個子串的最長公共前后綴長度，因此：
                      next[i] = next[i-1] + 1 等價于 next[i] = ++len
                 */

                // 等價于 next[i] = next[i-1] + 1
                next[i] = ++len;
                //既然找到了索引在[0,i]的子串的最長公共前后綴字符串長度，那就 i+1 去判斷以下一個字符結(jié)尾的子串的最長公共前后綴長度
                i++;
            } else {
                /*
                    1.如果不相等 patternArr[len]!=patternArr[i]
                      我們想要求當(dāng)前子串 對應(yīng)索引[0,i] 的最長公共前后綴長度
                      我們就不能以 上一個子串的最長公共前后綴：前綴字符串pre  后綴字符串post （毫無疑問pre==post） 作為拼接參考

                    2.但可以思考一下：
                      pre的最長公共前綴字符串： 索引 [      0        , next[len-1] )
                      是等于
                      post的最長公共后綴字符串：索引 [ i-next[len-1] ,     i       )

                      則我們 就以 pre的最長公共前綴字符串/post的最長公共后綴字符串 作為拼接參考
                      去判斷 pre的最長公共前綴字符串的下一個字符patternArr[next[len-1]] 是否等于 post的最長公共后綴字符串的下一個字符patternArr[i]

                    3.在第 1,2 步分析的基礎(chǔ)上
                      我們可以在判斷出 patternArr[len]!=patternArr[i] 后，
                      不去執(zhí)行第二步：patternArr[next[len-1]] 是否等于 patternArr[i]，
                      可以先修改len的值：len = next[len-1]，len就成了 pre的最長公共前綴字符串長度/post的最長公共后綴字符串長度，
                      修改完之后，再去判斷下一個字符 是否相等，即 判斷 patternArr[len] 是否等于 patternArr[i]
                      仔細觀察，這不又是在判斷 這個循環(huán)中 if-else 語句嗎

                    4.關(guān)于 len 這個值，在循環(huán)開始時我們解釋的是：上一個子串的最長公共前后綴字符串的長度
                      但實際上我們在這里改為 len = next[len-1] 表示上一個子串的最長公共前后綴字符串的最長公共前后綴字符串的長度
                      是沒有問題的，等價于上一個子串的較小的公共前后綴字符串。
                      既然進入了 else 語句說明字符不相等，就不能以 上一個子串的最長公共前后綴字符串 作為 拼接參考，就應(yīng)當(dāng)去縮小參考范圍。
                 */
                if (len == 0) {

                    /*
                        len為0說明上一個子串已經(jīng)沒有了公共前后綴字符串
                        則我們沒有繼續(xù)尋找的必要 --> 索引在[0, i]的當(dāng)前子串的最長公共前后綴字符串長度就是0
                     */
                    next[i] = len;

                    //繼續(xù)尋找下一個字符串的最長公共前后綴字符串長度
                    i++;

                } else {
                    len = next[len - 1];
                }

            }
        }

        return next;
    }
}

3.2 允許匹配多個，可重復(fù)索引字符的代碼

3.2.1 KMP算法的大致步驟

1. 求出模式字符串patternStr的部分匹配表，已知待匹配的字符串 matchStr
2. 定義兩個指針 i 和 j，分別指向 patternStr 和 matchStr ，初始化為0
3. 定義一個 ArrayList 集合 firstIndexList，用于存儲每次匹配成功的字符串的開始索引位置
4. 判斷 patternStr[i] 和 matchStr[j] 是否相等
   • 如果相等，則繼續(xù)向后匹配：i++, j++
   • 如果不相等，則 i 不變，調(diào)整 j 為 模式字符串pattern? 的 上一個子串（索引 [ 0, j-1 ]）的最長公共前綴字符串的下一個索引位置，該索引位置也是最長公共前綴/后綴字符串的長度：j = next[ j - 1 ]
5. 判斷 i 是否超出 最大索引值
   • 如果超出了 matchStr 的 最大索引值，就退出循環(huán)
6. 判斷 j 是否超出了 最大索引值
   • 如果超出了 patternStr 的最大索引值：
     • 將匹配到的字符串的開始索引位置加入到 firstIndexList 集合：firstIndexList.add( i - j )
     • 調(diào)整 j 為 模式字符串pattern （索引 [ 0, j-1 ]）的最長公共前綴字符串的下一個索引位置，該索引位置也是最長公共前綴/后綴字符串的長度：j = next[ j - 1 ]。
7. 第五步成立則循環(huán)退出，返回 firstIndexList 集合

3.2.2 代碼實現(xiàn)+測試

package kmp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 狐貍半面添
 * @create 2022-11-22 22:43
 */
public class KMPAlgorithm {
    public static void main(String[] args) {
        String matchStr = "AABABADDABAC";
        String patternStr = "ABA";

        // 輸出：[1, 3, 8]
        System.out.println(kmpSearch(matchStr, patternStr, kmpNext(patternStr)).toString());

    }

    /**
     * kmp搜索算法
     *
     * @param matchStr   原字符串
     * @param patternStr 子串
     * @param next       子串對應(yīng)的部分匹配表
     * @return 每次匹配成功的字符串的開始索引位置的集合
     */
    public static ArrayList<Integer> kmpSearch(String matchStr, String patternStr, int[] next) {

        int i = 0, j = 0;

        ArrayList<Integer> firstIndexList = new ArrayList<>();

        while (i < matchStr.length()) {

            if (matchStr.charAt(i) == patternStr.charAt(j)) {
                //相等就繼續(xù)進行匹配
                i++;
                j++;

            } else {
                //如果 patternStr[i] 和 matchStr[j] 不相等

                if (j == 0) {
                    /*
                        表示 matchStr 沒有匹配到 patternStr的第一個字符
                        那直接將 matchStr 的指針 i 向后移動一位即可
                     */
                    i++;
                } else {
                    j = next[j - 1];
                }
            }

            if (j == patternStr.length()) {
                //超出了最大索引值
                firstIndexList.add(i - j);
                j = next[j - 1];
            }

        }
        return firstIndexList;
    }

    /**
     * 獲取一個字符串 pattern 的部分匹配表
     *
     * @param patternStr 用于模式匹配字符串
     * @return 存儲部分匹配表的每個子串的最長公共前后綴的 next數(shù)組
     */
    public static int[] kmpNext(String patternStr) {
        //將 patternStr 轉(zhuǎn)為 字符數(shù)組形式
        char[] patternArr = patternStr.toCharArray();

        //預(yù)先創(chuàng)建一個next數(shù)組，用于存儲部分匹配表的每個子串的最長公共前后綴
        int[] next = new int[patternStr.length()];

        /*
            從第一個字符（對應(yīng)索引為0）開始的子串，如果子串的長度為1，那么肯定最長公共前后綴為0
            因為這唯一的一個字符既是第一個字符，又是最后一個字符，所以前后綴都不存在 -> 最長公共前后綴為0
         */
        next[0] = 0;

        /*
          len有兩個作用：
            1. 用于記錄當(dāng)前子串的最長公共前后綴長度
            2. 同時知道當(dāng)前子串的最長公共前后綴的前綴字符串對應(yīng)索引 [0,len-1]  <-- 可以拿示例分析一下
         */
        int len = 0;

        //從第二個字符開始遍歷，求索引在 [0,i] 的子串的最長公共前后綴長度
        int i = 1;
        while (i < patternArr.length) {
            /*
                1.已經(jīng)知道了上一個子串 對應(yīng)索引[0,i-1] 的最長公共前后綴長度為 len
                  的前綴字符串是 索引[0,len-1]，對應(yīng)相等的后綴字符串是 索引[i-len,i-1]

                2.因此我們可以以 上一個子串的最長公共前后綴字符串 作為拼接參考
                  比較一下 patternArr[len] 與 patternArr[i] 是否相等
             */
            if (patternArr[len] == patternArr[i]) {
                /*
                    1.如果相等即 patternArr[len]==patternArr[i]，
                      那么就可以確定當(dāng)前子串的最長公共前后綴的
                      前綴字符串是 索引[0,len] ，對應(yīng)相等的后綴字符串是 索引[i-len,i]

                    2.由于是拼接操作，那么當(dāng)前子串的最長公共前后綴長度只需要在上一個子串的最長公共前后綴長度的基礎(chǔ)上 +1 即可
                      即 next[i] = next[i-1] + 1 ，

                    3.由于 len 是記錄的子串的最長公共前后綴長度，對于當(dāng)前我們所在的代碼位置而言
                      len 還是記錄的上一個子串的最長公共前后綴長度，因此：
                      next[i] = next[i-1] + 1 等價于 next[i] = ++len
                 */

                // 等價于 next[i] = next[i-1] + 1
                next[i] = ++len;
                //既然找到了索引在[0,i]的子串的最長公共前后綴字符串長度，那就 i+1 去判斷以下一個字符結(jié)尾的子串的最長公共前后綴長度
                i++;
            } else {
                /*
                    1.如果不相等 patternArr[len]!=patternArr[i]
                      我們想要求當(dāng)前子串 對應(yīng)索引[0,i] 的最長公共前后綴長度
                      我們就不能以 上一個子串的最長公共前后綴：前綴字符串pre  后綴字符串post （毫無疑問pre==post） 作為拼接參考

                    2.但可以思考一下：
                      pre的最長公共前綴字符串： 索引 [      0        , next[len-1] )
                      是等于
                      post的最長公共后綴字符串：索引 [ i-next[len-1] ,     i       )

                      則我們 就以 pre的最長公共前綴字符串/post的最長公共后綴字符串 作為拼接參考
                      去判斷 pre的最長公共前綴字符串的下一個字符patternArr[next[len-1]] 是否等于 post的最長公共后綴字符串的下一個字符patternArr[i]

                    3.在第 1,2 步分析的基礎(chǔ)上
                      我們可以在判斷出 patternArr[len]!=patternArr[i] 后，
                      不去執(zhí)行第二步：patternArr[next[len-1]] 是否等于 patternArr[i]，
                      可以先修改len的值：len = next[len-1]，len就成了 pre的最長公共前綴字符串長度/post的最長公共后綴字符串長度，
                      修改完之后，再去判斷下一個字符 是否相等，即 判斷 patternArr[len] 是否等于 patternArr[i]
                      仔細觀察，這不又是在判斷 這個循環(huán)中 if-else 語句嗎

                    4.關(guān)于 len 這個值，在循環(huán)開始時我們解釋的是：上一個子串的最長公共前后綴字符串的長度
                      但實際上我們在這里改為 len = next[len-1] 表示上一個子串的最長公共前后綴字符串的最長公共前后綴字符串的長度
                      是沒有問題的，等價于上一個子串的較小的公共前后綴字符串。
                      既然進入了 else 語句說明字符不相等，就不能以 上一個子串的最長公共前后綴字符串 作為 拼接參考，就應(yīng)當(dāng)去縮小參考范圍。
                 */
                if (len == 0) {

                    /*
                        len為0說明上一個子串已經(jīng)沒有了公共前后綴字符串
                        則我們沒有繼續(xù)尋找的必要 --> 索引在[0, i]的當(dāng)前子串的最長公共前后綴字符串長度就是0
                     */
                    next[i] = len;

                    //繼續(xù)尋找下一個字符串的最長公共前后綴字符串長度
                    i++;

                } else {
                    len = next[len - 1];
                }

            }
        }

        return next;
    }
}

3.3 允許匹配多個，不可重復(fù)索引字符的代碼

3.3.1 KMP算法的大致步驟

1. 求出模式字符串patternStr的部分匹配表，已知待匹配的字符串 matchStr
2. 定義兩個指針 i 和 j，分別指向 patternStr 和 matchStr ，初始化為0
3. 定義一個 ArrayList 集合 firstIndexList，用于存儲每次匹配成功的字符串的開始索引位置
4. 判斷 patternStr[i] 和 matchStr[j] 是否相等
   • 如果相等，則繼續(xù)向后匹配：i++, j++
   • 如果不相等，則 i 不變，調(diào)整 j 為 模式字符串pattern? 的 上一個子串（索引 [ 0, j-1 ]）的最長公共前綴字符串的下一個索引位置，該索引位置也是最長公共前綴/后綴字符串的長度：j = next[ j - 1 ]
5. 判斷 i 是否超出 最大索引值
   • 如果超出了 matchStr 的 最大索引值，就退出循環(huán)
6. 判斷 j 是否超出了 最大索引值
   • 如果超出了 patternStr 的最大索引值：
     • 將匹配到的字符串的開始索引位置加入到 firstIndexList 集合：firstIndexList.add( i - j )
     • 設(shè)置 j = 0 開始重新匹配
7. 第五步成立則循環(huán)退出，返回 firstIndexList 集合

3.3.2 代碼實現(xiàn)+測試

package kmp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 狐貍半面添
 * @create 2022-11-22 22:43
 */
public class KMPAlgorithm {
    public static void main(String[] args) {
        String matchStr = "AABABADDABAC";
        String patternStr = "ABA";

        // 輸出：[1, 8]
        System.out.println(kmpSearch(matchStr, patternStr, kmpNext(patternStr)).toString());

    }

    /**
     * kmp搜索算法
     *
     * @param matchStr   原字符串
     * @param patternStr 子串
     * @param next       子串對應(yīng)的部分匹配表
     * @return 每次匹配成功的字符串的開始索引位置的集合
     */
    public static ArrayList<Integer> kmpSearch(String matchStr, String patternStr, int[] next) {

        int i = 0, j = 0;

        ArrayList<Integer> firstIndexList = new ArrayList<>();

        while (i < matchStr.length()) {

            if (matchStr.charAt(i) == patternStr.charAt(j)) {
                //相等就繼續(xù)進行匹配
                i++;
                j++;

            } else {
                //如果 patternStr[i] 和 matchStr[j] 不相等

                if (j == 0) {
                    /*
                        表示 matchStr 沒有匹配到 patternStr的第一個字符
                        那直接將 matchStr 的指針 i 向后移動一位即可
                     */
                    i++;
                } else {
                    j = next[j - 1];
                }
            }

            if (j == patternStr.length()) {
                //超出了最大索引值
                firstIndexList.add(i - j);
                j = 0;
            }

        }
        return firstIndexList;
    }

    /**
     * 獲取一個字符串 pattern 的部分匹配表
     *
     * @param patternStr 用于模式匹配字符串
     * @return 存儲部分匹配表的每個子串的最長公共前后綴的 next數(shù)組
     */
    public static int[] kmpNext(String patternStr) {
        //將 patternStr 轉(zhuǎn)為 字符數(shù)組形式
        char[] patternArr = patternStr.toCharArray();

        //預(yù)先創(chuàng)建一個next數(shù)組，用于存儲部分匹配表的每個子串的最長公共前后綴
        int[] next = new int[patternStr.length()];

        /*
            從第一個字符（對應(yīng)索引為0）開始的子串，如果子串的長度為1，那么肯定最長公共前后綴為0
            因為這唯一的一個字符既是第一個字符，又是最后一個字符，所以前后綴都不存在 -> 最長公共前后綴為0
         */
        next[0] = 0;

        /*
          len有兩個作用：
            1. 用于記錄當(dāng)前子串的最長公共前后綴長度
            2. 同時知道當(dāng)前子串的最長公共前后綴的前綴字符串對應(yīng)索引 [0,len-1]  <-- 可以拿示例分析一下
         */
        int len = 0;

        //從第二個字符開始遍歷，求索引在 [0,i] 的子串的最長公共前后綴長度
        int i = 1;
        while (i < patternArr.length) {
            /*
                1.已經(jīng)知道了上一個子串 對應(yīng)索引[0,i-1] 的最長公共前后綴長度為 len
                  的前綴字符串是 索引[0,len-1]，對應(yīng)相等的后綴字符串是 索引[i-len,i-1]

                2.因此我們可以以 上一個子串的最長公共前后綴字符串 作為拼接參考
                  比較一下 patternArr[len] 與 patternArr[i] 是否相等
             */
            if (patternArr[len] == patternArr[i]) {
                /*
                    1.如果相等即 patternArr[len]==patternArr[i]，
                      那么就可以確定當(dāng)前子串的最長公共前后綴的
                      前綴字符串是 索引[0,len] ，對應(yīng)相等的后綴字符串是 索引[i-len,i]

                    2.由于是拼接操作，那么當(dāng)前子串的最長公共前后綴長度只需要在上一個子串的最長公共前后綴長度的基礎(chǔ)上 +1 即可
                      即 next[i] = next[i-1] + 1 ，

                    3.由于 len 是記錄的子串的最長公共前后綴長度，對于當(dāng)前我們所在的代碼位置而言
                      len 還是記錄的上一個子串的最長公共前后綴長度，因此：
                      next[i] = next[i-1] + 1 等價于 next[i] = ++len
                 */

                // 等價于 next[i] = next[i-1] + 1
                next[i] = ++len;
                //既然找到了索引在[0,i]的子串的最長公共前后綴字符串長度，那就 i+1 去判斷以下一個字符結(jié)尾的子串的最長公共前后綴長度
                i++;
            } else {
                /*
                    1.如果不相等 patternArr[len]!=patternArr[i]
                      我們想要求當(dāng)前子串 對應(yīng)索引[0,i] 的最長公共前后綴長度
                      我們就不能以 上一個子串的最長公共前后綴：前綴字符串pre  后綴字符串post （毫無疑問pre==post） 作為拼接參考

                    2.但可以思考一下：
                      pre的最長公共前綴字符串： 索引 [      0        , next[len-1] )
                      是等于
                      post的最長公共后綴字符串：索引 [ i-next[len-1] ,     i       )

                      則我們 就以 pre的最長公共前綴字符串/post的最長公共后綴字符串 作為拼接參考
                      去判斷 pre的最長公共前綴字符串的下一個字符patternArr[next[len-1]] 是否等于 post的最長公共后綴字符串的下一個字符patternArr[i]

                    3.在第 1,2 步分析的基礎(chǔ)上
                      我們可以在判斷出 patternArr[len]!=patternArr[i] 后，
                      不去執(zhí)行第二步：patternArr[next[len-1]] 是否等于 patternArr[i]，
                      可以先修改len的值：len = next[len-1]，len就成了 pre的最長公共前綴字符串長度/post的最長公共后綴字符串長度，
                      修改完之后，再去判斷下一個字符 是否相等，即 判斷 patternArr[len] 是否等于 patternArr[i]
                      仔細觀察，這不又是在判斷 這個循環(huán)中 if-else 語句嗎

                    4.關(guān)于 len 這個值，在循環(huán)開始時我們解釋的是：上一個子串的最長公共前后綴字符串的長度
                      但實際上我們在這里改為 len = next[len-1] 表示上一個子串的最長公共前后綴字符串的最長公共前后綴字符串的長度
                      是沒有問題的，等價于上一個子串的較小的公共前后綴字符串。
                      既然進入了 else 語句說明字符不相等，就不能以 上一個子串的最長公共前后綴字符串 作為 拼接參考，就應(yīng)當(dāng)去縮小參考范圍。
                 */
                if (len == 0) {

                    /*
                        len為0說明上一個子串已經(jīng)沒有了公共前后綴字符串
                        則我們沒有繼續(xù)尋找的必要 --> 索引在[0, i]的當(dāng)前子串的最長公共前后綴字符串長度就是0
                     */
                    next[i] = len;

                    //繼續(xù)尋找下一個字符串的最長公共前后綴字符串長度
                    i++;

                } else {
                    len = next[len - 1];
                }

            }
        }

        return next;
    }
}

到了這里，關(guān)于KMP算法——通俗易懂講好KMP算法：實例圖解分析+詳細代碼注解 --》你的所有疑惑在本文都能得到解答的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！