1.0 BF 算法概述

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

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

1.1 BF 算法實(shí)際使用

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

實(shí)現(xiàn)思路：為了實(shí)現(xiàn)一個(gè)比較嚴(yán)謹(jǐn)?shù)某绦?，首先?str 與 sub 進(jìn)行判斷是否為 null 或者長度為 0 。

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

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

如圖：

最后，判斷是什么原因?qū)е绿隽搜h(huán)：

有兩個(gè)原因：（1）j >= subLen ，則說明了 j 已經(jīng)比較完畢了，所以主串中存在子串，位置位于：（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;
        }

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

        //記錄子串下標(biāo)
        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 算法概述

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

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

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

2.1 KMP 算法實(shí)際使用

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

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

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

2.2 相比于 BF 算法實(shí)現(xiàn)，KMP 算法的重要思想

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

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

2.3 為什么要這樣設(shè)計(jì)？

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

如圖：

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

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

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

到底原理是為啥呢？

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

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

發(fā)現(xiàn) str.charAt(i) == sub.charAt(j) 時(shí)，i++，j++ ，一直到結(jié)束為止。

2.4 next 數(shù)組

剛剛上面提到了當(dāng)遇到 str.charAt(i) == sub.charAt(j) 時(shí)，i 保持不變而 j 會(huì)跳到指定的位置。而這個(gè)指定的位置就是 j 對應(yīng)下標(biāo)的位置 j = next[j] 。

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

舉個(gè)例子來演示

初始化為：

next 數(shù)組中，索引為 0 和索引為 1 分別設(shè)置為 -1 和 0。

接著，到字符 c 的索引下標(biāo)了，先判斷字符 c 前面的字符串有無以 a 開頭且以 b 結(jié)尾的兩個(gè)不重復(fù)的字符串。顯然，這里就兩個(gè)字符 a b ，沒有找到相同的以 a 開頭，且以 b 結(jié)尾的兩個(gè)相同且可以不完全重疊的字符串。那么字符 c 的 next 對應(yīng)就為 0 。

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

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

再接著，到子串索引為 5 處的字符 c ，先判斷 c 字符前面的 a b c a b 有無以 a 開頭且以 b 結(jié)尾的兩個(gè)不相同且不完全重疊的字符串。可以明顯的發(fā)現(xiàn) ab 與 ab 滿足，長度為 2 ,那么對應(yīng)到 next 數(shù)組中為 2 。

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

再來講講具體如何使用 next 數(shù)組。

接著上一個(gè)例子：

此時(shí) str.charAt(i) != sub.charAt(j) ，那么 i 保持不動(dòng)，j 就會(huì)根據(jù) next 數(shù)組來回到指定的地方，此時(shí) j = next[j] 。因?yàn)?j 的值為 5，在 next[5] 中所對應(yīng)的索引為 2 。

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

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

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

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

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

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

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

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

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

舉個(gè)例子：

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

此時(shí) k = 0，i = 3 。

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

此時(shí) k = 0，i = 4 。

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

此時(shí) next[4] = 1，k = 1，i = 5 。

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

此時(shí) next[5] = 2，k = 2， i = 5 。

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

2.5 KMP 算法的實(shí)現(xiàn)

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

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

2）next 數(shù)組的創(chuàng)建，首先初始化 next 數(shù)組，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] 。

需要注意的是，當(dāng)出現(xiàn) k == -1 特殊情況的時(shí)候，該處理方式為 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" );
        }

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

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

        //next 數(shù)組，存放的是子串與主串不適配所需要 j 回溯的索引下標(biāo),長度為字串的長度
        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 {
                //當(dāng)不相同的時(shí)候，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 {
                //如果不相同，那么會(huì)繼續(xù)接著找，直到相同為止或者k==-1為止
                k = next[k];
            }
        }
    }
}

總結(jié) 

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

最新評論