1.BF算法

1.1 定義

BF(Brute Force)算法,中文叫作暴力匹配算法，也叫樸素匹配算法。
思想:在主串中，檢查起始位置分別是 0、1、2…n-m 且長(zhǎng)度為 m 的 n-m+1 個(gè)子串，看有沒(méi)有跟模式串匹配的。

image.png

1.2 性能分析

算法的最壞情況下的時(shí)間復(fù)雜度為O(n*m)。

1.3 實(shí)際場(chǎng)景

在實(shí)際的開發(fā)中，是一個(gè)比較常用的字符串匹配算法：
第一，實(shí)際的軟件開發(fā)中，大部分情況下，模式串和主串的長(zhǎng)度都不會(huì)太長(zhǎng)。而且每次模式串與主串中的子串匹配的時(shí)候，當(dāng)中途遇到不能匹配的字符的時(shí)候，就可以就停止了，不需要把 m 個(gè)字符都比對(duì)一下。所以，盡管理論上的最壞情況時(shí)間復(fù)雜度是 O(n*m)，但是，統(tǒng)計(jì)意義上，大部分情況下，算法執(zhí)行效率要比這個(gè)高很多。
第二，樸素字符串匹配算法思想簡(jiǎn)單，代碼實(shí)現(xiàn)也非常簡(jiǎn)單。簡(jiǎn)單意味著不容易出錯(cuò)，如果有 bug 也容易暴露和修復(fù)。在工程中，在滿足性能要求的前提下，簡(jiǎn)單是首選。這也是我們常說(shuō)的KISS（Keep it Simple and Stupid）設(shè)計(jì)原則。

1.4代碼實(shí)現(xiàn)

     /**
     * BK實(shí)現(xiàn)的字符串匹配，返回符合的下標(biāo)，不存在則返回-1
     * @param strMaster 主串
     * @param strSlave  模式串
     * @return
     */
    public static int indexOf(String strMaster, String strSlave) {
        // 校驗(yàn)
        if (strMaster == null || strSlave == null || strMaster.length() < strSlave.length()) {
            return -1;
        }
        int n = strMaster.length();
        int m = strSlave.length();
        //對(duì)于主串長(zhǎng)度為n，子串長(zhǎng)度為m，一共可以比較n-m+1次
        for (int i = 0; i <= n - m + 1; i++) {
            // 比較
            int j = 0;
            for (; j < m; j++) {
                if (strMaster.charAt(j + i) != strSlave.charAt(j)) {
                    break;
                }
            }
            // 找到符合的匹配字符串的標(biāo)志
            if (j == m ) {
                return i;
            }
        }
        return -1;
    }

RK算法

1.定義

BF算法:每次檢查主串與子串是否匹配，需要依次比對(duì)每個(gè)字符，所以 BF 算法的時(shí)間復(fù)雜度就比較高，是 O(n*m)。我們對(duì)樸素的字符串匹配算法稍加改造，引入哈希算法，時(shí)間復(fù)雜度立刻就會(huì)降低。

RK算法思想:我們通過(guò)哈希算法對(duì)主串中的 n-m+1 個(gè)子串分別求哈希值，然后逐個(gè)與模式串的哈希值比較大小。如果某個(gè)子串的哈希值與模式串相等，那就說(shuō)明對(duì)應(yīng)的子串和模式串匹配了（這里先不考慮哈希沖突的問(wèn)題）。因?yàn)楣Ｖ凳且粋€(gè)數(shù)字，數(shù)字之間比較是否相等是非?？焖俚?，所以模式串和子串比較的效率就提高了。

設(shè)計(jì)哈希函數(shù)

通過(guò)哈希算法計(jì)算子串的哈希值的時(shí)候，我們需要遍歷子串中的每個(gè)字符。盡管模式串與子串比較的效率提高了，但是整體的算法效率并沒(méi)有提高；
涉及思路:

我們假設(shè)要匹配的字符串的字符集中只包含 K 個(gè)字符，我們可以用一個(gè) K 進(jìn)制數(shù)來(lái)表示一個(gè)子串，這個(gè) K 進(jìn)制數(shù)轉(zhuǎn)化成十進(jìn)制數(shù)，作為子串的哈希值。

三個(gè)tips:

• 比如要處理的字符串只包含 a～z 這 26 個(gè)小寫字母，那我們就用二十六進(jìn)制來(lái)表示一個(gè)字符串。我們把 a～z 這 26 個(gè)字符映射到 0～25 這 26 個(gè)數(shù)字，a 就表示 0，b 就表示 1，以此類推，z 表示 25。

  
  
  image.png

• 這種哈希算法有一個(gè)特點(diǎn)，在主串中，相鄰兩個(gè)子串的哈希值的計(jì)算公式有一定關(guān)系.
  相鄰兩個(gè)子串 s[i-1]和 s[i]（i 表示子串在主串中的起始位置，子串的長(zhǎng)度都為 m），對(duì)應(yīng)的哈希值計(jì)算公式有交集，也就是說(shuō)，我們可以使用 s[i-1]的哈希值很快的計(jì)算出 s[i]的哈希值:

  
  
  image.png

• 那就是 26^(m-1) 這部分的計(jì)算，我們可以通過(guò)查表的方法來(lái)提高效率。我們事先計(jì)算好 26^0、261、26^2……26(m-1)，并且存儲(chǔ)在一個(gè)長(zhǎng)度為 m 的數(shù)組中，公式中的“次方”就對(duì)應(yīng)數(shù)組的下標(biāo)。當(dāng)我們需要計(jì)算 26 的 x 次方的時(shí)候，就可以從數(shù)組的下標(biāo)為 x 的位置取值，直接使用，省去了計(jì)算的時(shí)間。

2.實(shí)現(xiàn)

public static int rk(String strMas, String strSla) {
        // 健壯性判斷(略過(guò))
        // 主串的長(zhǎng)度及對(duì)應(yīng)的字符數(shù)組
        int n = strMas.length();
        char[] charMas = strMas.toCharArray();
        // 模式串的長(zhǎng)度及對(duì)應(yīng)的字符數(shù)組
        int m = strSla.length();
        char[] charSla = strSla.toCharArray();
        // 新建長(zhǎng)度為26的數(shù)組，存儲(chǔ)進(jìn)制，會(huì)溢出，但是也沒(méi)有問(wèn)題，使用進(jìn)制的目的就是保證不會(huì)重復(fù)
        int[] table = new int[26];
        table[0] = 1;
        for (int i = 1; i < 26; i++) {
            table[i] = table[i - 1] * 26;
        }
        // 新建數(shù)組，存儲(chǔ)主串需要比較的n-m+1個(gè)子串的哈希值
        int[] hash = new int[n - m + 1];
        // 先計(jì)算出第一個(gè)子串的哈希值，從[0,m-1],table表示位數(shù)，最高位為[m-1]
        for (int i = 0; i <= m - 1; i++) {
            hash[0] = hash[0] + (charMas[i] - 'a') * table[m - 1 - i];
        }
        // hash[]從1開始
        for (int i = 1; i <= n - m; i++) {
            // 使用技巧公式
            hash[i] = (hash[i - 1] - (charMas[i - 1] - 'a') * table[m - 1]) * 26 + (charMas[i + m - 1] - 'a');
        }
        // 計(jì)算模式串的哈希值
        int hashSla = 0;
        for (int i = 0; i <= m - 1; i++) {
            hashSla = hashSla + (charSla[i] - 'a') * table[m - 1 - i];
        }
        // 前戲準(zhǔn)備完成，開始比較
        for (int i = 0; i < n - m + 1; i++) {
            if (hash[i] == hashSla) {
                return i;
            }
        }
        return -1;
    }

3.復(fù)雜度分析

整個(gè) RK 算法包含兩部分，計(jì)算子串哈希值和模式串哈希值與子串哈希值之間的比較。
對(duì)于計(jì)算子串哈希值可以通過(guò)設(shè)計(jì)特殊的哈希算法，只需要掃描一遍主串就能計(jì)算出所有子串的哈希值了，所以這部分的時(shí)間復(fù)雜度是 O(n)。
模式串哈希值與每個(gè)子串哈希值之間的比較的時(shí)間復(fù)雜度是 O(1)，總共需要比較 n-m+1 個(gè)子串的哈希值，所以，這部分的時(shí)間復(fù)雜度也是 O(n)。
所以，RK 算法整體的時(shí)間復(fù)雜度就是 O(n)。

4.改進(jìn)

模式串很長(zhǎng)，相應(yīng)的主串中的子串也會(huì)很長(zhǎng)，通過(guò)上面的哈希算法計(jì)算得到的哈希值就可能很大，如果超過(guò)了計(jì)算機(jī)中整型數(shù)據(jù)可以表示的范圍，那該如何解決呢？

在之前設(shè)計(jì)的哈希算法是沒(méi)有散列沖突的，也就是說(shuō)，一個(gè)字符串與一個(gè)二十六進(jìn)制數(shù)一一對(duì)應(yīng)，不同的字符串的哈希值肯定不一樣。因?yàn)槲覀兪腔谶M(jìn)制來(lái)表示一個(gè)字符串的。

方案:

• 重新設(shè)計(jì)哈希算法
• 對(duì)于哈希值不一致的，字符串肯定不一樣，直接跳過(guò)；
• 對(duì)于哈希值一樣的，再進(jìn)行比較一次確定；
• 所有對(duì)于哈希函數(shù)的設(shè)計(jì)很有講究，如果哈希沖突太多，RK算法在極端情況下會(huì)退化為BK算法。