1.0 BF 算法概述

是一種基本的暴力搜索算法，也稱為窮舉算法或暴力匹配算法。BF 算法通過遍歷所有可能的解空間來尋找問題的解，雖然效率較低，但在一些簡單的問題上仍然具有一定的實用性。

盡管 BF 算法效率較低，但在一些簡單的問題上，它仍然可以提供可行的解決方案。在一些小規(guī)模的問題、教學示例或者需要快速驗證解的情況下，BF 算法可以作為一種簡單且直觀的解決方法。

1.1 BF 算法實際使用

 舉個例子：用 BF 算法來找到主串 str 中是否存在子串 sub，如果存在，那么子串在主串的具體那個位置。

實現思路：為了實現一個比較嚴謹的程序，首先對 str 與 sub 進行判斷是否為 null 或者長度為 0 。

接著，用變量 i 來記錄主串 str 索引下標，用變量 j 來記錄子串 sub 索引下標，且用 strLen 來記錄主串的長度，用 sunLen 來記錄子串的長度。

再接著，用 while 循環(huán)，循環(huán)比較 str 與 sub 中字符是否相同，如 str.charAt(i) 與 sub.charAt(j) 進行比較，如果兩者相同，那么繼續(xù)往后走 i++ ，j++  ；如果兩者不相同，那么對于主串來說，i 需要回到 i = i - j + 1 位置，對于 j 來說， 就要回到原點 j = 0 。

如圖：

最后，判斷是什么原因導致跳出了循環(huán)：

有兩個原因：（1）j >= subLen ，則說明了 j 已經比較完畢了，所以主串中存在子串，位置位于：（i - j）。（2）i > strLen ，則說明，即使 i 都走完了， j 還沒走完，那么主串中不存在該子串。

代碼如下：

public class demo1 {
    //暴力解法
    public static void main(String[] args) {
        String str = "abbccccfffrreytur";
        String sub = "tu";
        bf(str,sub);
    }
    public static void bf(String str, String sub){
        if (str == null || sub == null){
            System.out.println("對象為 null");
            return;
        }
        if (str.length() == 0 || sub.length() == 0){
            System.out.println("長度不合法！?。。?);
            return;
        }

        //記錄主串下標
        int i = 0;
        //主串長度
        int strLen = str.length();

        //記錄子串下標
        int j = 0;
        //子串長度
        int subLen = sub.length();

        while (i < strLen && j < subLen){
            if (str.charAt(i) == sub.charAt(j)){
                i++;
                j++;
            }else {
                //如果不相同了，那么 i 就要回頭再來找，而對于 j 就要重頭開始了
                i = i - j + 1;
                j = 0;
            }
        }
        if (subLen <= j){
            System.out.println("找到子串再主串的位置了:" + (i-j) + " 到 " + (i-1));
        }else {
            System.out.println("沒找到?。。?！");
        }
    }
}

2.0 KMP 算法概述

是一種高效的字符串匹配算法，用于在一個主串中查找一個模式串的出現位置。KMP 算法的核心思想是利用已匹配的信息來盡量減少不必要的比較，從而提高匹配效率。

KMP 算法的時間復雜度為 O(m+n)，其中 m 是主串的長度，n 是模式串的長度。相比于 BF 暴力匹配算法，KMP 算法具有更高的效率，尤其在處理大規(guī)模文本匹配時表現優(yōu)異。

簡單來說，KMP 算法比 BF 算法有更高的效率，是 BF 一個升級的算法。

2.1 KMP 算法實際使用

同樣繼續(xù)用到 BF 算法的例子。

舉個例子：用 BF 算法來找到主串 str 中是否存在子串 sub，如果存在，那么子串在主串的具體那個位置。

用變量 i 來記錄主串 str 索引下標，用變量 j 來記錄子串 sub 索引下標，且用 strLen 來記錄主串的長度，用 sunLen 來記錄子串的長度。

2.2 相比于 BF 算法實現，KMP 算法的重要思想

對于 i 來說：i 不后退，i 一直進行的是 i++ ，即使遇到 str.charAt(i) != sub.charAt(j)  ，i 也不會后退。

對于 j 來說：當字符都相同 str.charAt(i) == sub.charAt(j) 時，那么 j++ ；當字符不相同 str.charAt(i) != sub.charAt(j) 時，那么 j 會回退到指定的位置，不一定是 0 索引位置。（在 BF 算法中 j 當遇到不相同的時候，一定會回退到 0 索引位置處）

2.3 為什么要這樣設計？

為了在主串與子串匹配的時候，提高效率。

如圖：

如果按照 BF 算法來設計，那么 i 就會回到索引為 1 位置 b 處，而 j 就要回到索引為 0 位置 a 處。

而對于 KMP 算法設計來說，當兩個字符不相同的時候，i 不用后退，j 不一定退回到索引為 0 處，假設 j 退回到索引為 2 位置 c 處。

先觀察兩個圈的位置，從當 j 回到索引為 2 位置 c 處，可以發(fā)現子串前面的兩個字符與主串的對應的兩個字符是一樣的，這樣就避免了 BF 算法的冗余的比較。

到底原理是為啥呢？

發(fā)現 a != c 了，但是前面部分肯定是相同的，不然都不會來到此處，那么主串 str 就想著嘗試去在 sub 其他位置（除了當前紅圈位置的 ab ）中找到與主串前部分有沒有相同的子字符串，當前就找到了（子串藍圈部分），那么既然前部分 ab 相同，就不需要比較了，當前比較的是藍色圈后一個字符是否相同。

當前來看，是不相同的。那么 i 繼續(xù)保持不動，j 繼續(xù)跳到指定的位置，那么假設跳到索引為 0 處的位置。

發(fā)現 str.charAt(i) == sub.charAt(j) 時，i++，j++ ，一直到結束為止。

2.4 next 數組

剛剛上面提到了當遇到 str.charAt(i) == sub.charAt(j) 時，i 保持不變而 j 會跳到指定的位置。而這個指定的位置就是 j 對應下標的位置 j = next[j] 。

2.4.1 創(chuàng)建 next 數組原理

舉個例子來演示

初始化為：

next 數組中，索引為 0 和索引為 1 分別設置為 -1 和 0。

接著，到字符 c 的索引下標了，先判斷字符 c 前面的字符串有無以 a 開頭且以 b 結尾的兩個不重復的字符串。顯然，這里就兩個字符 a b ，沒有找到相同的以 a 開頭，且以 b 結尾的兩個相同且可以不完全重疊的字符串。那么字符 c 的 next 對應就為 0 。

再接著，到子串索引為 3 處的字符 a ，先判斷該字符 a 前面的字符串 a b c 有無以 a 開頭且以 c 結尾的兩個相同且不完全重疊的字符串，很顯然是沒有的，同樣對應該 next 為 0 。

再接著，到子串索引為 4 處的字符 b ，先判斷 b 字符前面的 a b c a 無以 a 開頭且以 a 結尾的兩個相同且不完全重疊的字符串。這次發(fā)現了存在這樣的兩個字符串，a 與 a ，長度為 1 。那么對應到 next 數組為 1 。

再接著，到子串索引為 5 處的字符 c ，先判斷 c 字符前面的 a b c a b 有無以 a 開頭且以 b 結尾的兩個不相同且不完全重疊的字符串?？梢悦黠@的發(fā)現 ab 與 ab 滿足，長度為 2 ,那么對應到 next 數組中為 2 。

這樣 next 數組就創(chuàng)建完畢了。

再來講講具體如何使用 next 數組。

接著上一個例子：

此時 str.charAt(i) != sub.charAt(j) ，那么 i 保持不動，j 就會根據 next 數組來回到指定的地方，此時 j = next[j] 。因為 j 的值為 5，在 next[5] 中所對應的索引為 2 。

j 回到索引為 2 處，繼續(xù)比較 sub.charAt(j) 與 str.charAt(i) 是否相同。如果不相同，i 繼續(xù)保持不動，j 繼續(xù)根據 next 數組來給 j 賦值指定的索引；如果相同，那么 i++，j++。

以上這樣情況 a != c ，就要 j 重新賦值 j = next[j] ，則 j = 0 。

 j 回到索引 0 之后，繼續(xù)比較 sub.charAt(j) 與 str.charAt(i) 是否相同。如果相同，i++，j++ ；如果不相同，i 保持不動，j 就要根據 next 數組來找到對應的值 j = next[j] 。

以上該情況是相同的，那么直接 i++，j++ 即可。

補充：當 j = 0 時，發(fā)現 sub.charAt(0) 與 str.charAt(i) 還是不相同時，j 根據 next 數組來獲取值 j = next[j] 則 j = -1 。這種情況需要特殊考慮，當 j == -1 時，不能再繼續(xù)比較了，因為會出現數組越界問題，那么該情況應該進行 i++，j++ 操作處理。

2.4.2 創(chuàng)建 next 數組過程

1）初始化 next 數組：將 next 數組的第一個元素 next[0] 設置為 -1，next[1] 設置為 0。

2）遍歷模式串：從第二個位置開始（即 i=2），依次計算每個位置 i 處的 next 值。

3）計算 next 值：具體思路：定義 int k = 0， 從 i = 2 開始，判斷子串 sub[i - 1] 與 k 是否相同，如果相同，則 next[i] = k，i++，k++；如果不相同，則 k = next[k] ，直到找到 sub[i-1] 與 k 相同為止，或者 k == -1 為止。

舉個例子：

判斷 sub.charAt(k) 與 sub.charAt(i-1) 是否相同，a 與 b很顯然不相同，那么 k = next[k] 則 k = -1 ，那么 k == -1 的時候，next[i] = k+1，i++，j++ 。

此時 k = 0，i = 3 。

判斷 sub.charAt(k) 與 sub.charAt(i-1) 是否相同，a 與 c 很顯然不相同，那么 k = next[k] 則 k = -1 ，那么 k == -1 的時候，next[i] = k+1，i++，j++ 。

此時 k = 0，i = 4 。

判斷 sub.charAt(k) 與 sub.charAt(i-1) 是否相同，a 與 a 是相同的，那么 next[i] = k+1，i++，k++ 。

此時 next[4] = 1，k = 1，i = 5 。

判斷 sub.charAt(k) 與 sub.charAt(i-1) 是否相同，b 與 b 是相同的，那么 next[5] = k+1，k++，i++ 。

此時 next[5] = 2，k = 2， i = 5 。

最后 next 數組就創(chuàng)建完畢了。

2.5 KMP 算法的實現

1）在循環(huán)過程中，判斷主串與子串對應的字符是否相同，如果相同，繼續(xù)往下比較下去，直到子串遍歷完成，說明了主串中存在該子串；如果不相同，記錄主串下標的索引保持不變，而記錄子串下標的索引需要根據 next 數組來找到相對應的值，接著重新比較子串與主串中字符是否相同，如果相同，繼續(xù)往下比較；如果不相同，記錄子串下標的索引就要繼續(xù)根據 next 數組來找到指定的位置。

需要注意的是，當子串下標的索引為 -1 的時候，不能繼續(xù)往下比較了，該情況為特殊情況，需要進行的操作為：主串往后移動一次，子串的索引 + 1 處理。該特殊情況的操作，跟主串下標對應的字符與子串下標對應的字符相同的情況的操作處理是一致的。

2）next 數組的創(chuàng)建，首先初始化 next 數組，next[0] = -1，next[1] = 0 。定義 int k = 0，i = 2 ,判斷 sub.charAt(i-1) 與 sub.charAt(k) 是否相同，如果相同，next[i] = k+1，i++，k++ ；如果不相同，k = next[k] 。

需要注意的是，當出現 k == -1 特殊情況的時候，該處理方式為 next[i] = k+1，i++，k++ ，跟 sub.charAt(i-1) 與 sub.charAt(k) 相同處理操作的方式是一致的。

代碼如下：

public class demo1 {
    public static void main(String[] args) {
        String str = "abcccffggaaffggggkkkllrrr";
        String sub = "aaffk";
        kmp(str,sub);
    }

    public static void kmp(String str,String sub){
        if (str == null || sub == null){
            System.out.println("str 或者 sub 不合法");
            return;
        }
        if (str.length() == 0 || sub.length() == 0){
            System.out.println(str + " 或者 " + sub + " 長度為 0" );
        }

        //用來記錄主串的下標
        int i = 0;
        //記錄主串的長度
        int strLen = str.length();

        //用來記錄子串的下標
        int j = 0;
        //記錄子串的長度
        int subLen = sub.length();

        //next 數組，存放的是子串與主串不適配所需要 j 回溯的索引下標,長度為字串的長度
        int[] next = new int[subLen];
        getNext(next,sub);

        while (i < strLen && j < subLen){
            if ( j == -1 || str.charAt(i) == sub.charAt(j)){
                i++;
                j++;
            }else {
                //當不相同的時候，j 需要回溯到指定的地方
                j = next[j];
            }
        }
        //判斷退出循環(huán)的原因
        if (j >= subLen){
            System.out.println("找到該主串中子串的位置了:" + (i-j) + " 到 " + (i-1));
        }else {
            System.out.println("沒有找到！??！");
        }

    }

    public static void getNext(int[] next,String sub){
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int k = 0;
        int len = sub.length();
        while (i < len){
            if (k == -1 || sub.charAt(i-1) == sub.charAt(k)){
                next[i] = k+1;
                i++;
                k++;
            }else {
                //如果不相同，那么會繼續(xù)接著找，直到相同為止或者k==-1為止
                k = next[k];
            }
        }
    }
}

總結 

到此這篇關于Java算法篇之BF與KMP算法的文章就介紹到這了,更多相關Java BF與KMP算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論