字符串匹配算法之 BF 算法和 RK 算法

BF 算法

BF 是 Brute Force 的缩写，叫做暴力匹配算法，由名字就能看得出来，真的很暴力 😃，暴力的一般都是头脑简单四肢发达，时间复杂度比较高的那种。那我们就来看看究竟有多暴力吧！
在字符串匹配中有两个概念，煮串，不对，是主串和模式串，比如说有两个字符串 A、B，需求是要在字符串 A 中查找字符串 B，那么 A 就是主串，B 就是模式串。

BF 算法的脑回路是，主串和模式串从头部字符开始匹配，如果发现有匹配的，那模式串就向右移动一位，继续按照前面的规则匹配，至到能匹配到，匹配过程大致和下面类似:

是不是很暴力啊，想都不用想，实现方式里一定有两个循环，时间复杂度想都不用想，应该挺高的吧，那我们来分析一下。假设主串和模式串的长度分别是 n 和 m，根据上面的匹配过程我们可以分析出整个过程需要匹配 n-m+1 次，每次要进行 m 次的比对，那总共就需要(n-m+1) * m 比对，时间复杂度是 O(n*m)的，这要是字符串长度比较大的话，那就挂了哇。但是，在时间软件开发中确实比较常用的呢，难道是我们都傻了么，明明那么慢的算法，还用。有天有个大牛告诉我，现实不是这样的，而是这样的，

• 实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多
• 就是因为简单呀，当然是在满足性能要求条件下的话，简单就是最好的。

简单实现一下就是下面的喽:

public static int bF(String mainStr, String matStr) {
        int n = mainStr.length(), m = matStr.length(), k;
        if (m > n) {
            return -1;
        }
        char[] mainChars = mainStr.toCharArray();
        char[] matChars = matStr.toCharArray();
        // 外层循环控制向右滑动次数，i记录滑动位置
        for (int i = 0; i <= n - m; i++) {
            // k记录在一次比较过程中相等字符的个数
            k = 0;
            for (int j = 0; j < m; j++) {
                if (mainChars[i + j] == matChars[j]) {
                    k++;
                } else {
                    // 在一次比较过程中，如果有不相等的字符，就结束后次轮的比较，滑动进行下一轮的比较
                    break;
                }
            }
            // 判断再一次比较完结束后，相等字符的个数是否和模式串的个数相等，如果相等就说明匹配到了，
            // 如果不相等，就向右滑动，进行下一轮比较
            if (k == m) {
                return i;
            }
        }
        return -1;
    }
​

RK 算法

全称叫 Rabin-Karp 算,两个人名字的结合，诞生的。。
在 BF 算法中，其实就是取主串的 n-m+1 个子串和模式串进行一一比对，主要消耗就集中在子串和模式串挨个字符的比较，如果每个字符都计算一个固定的值，再和模式串使用同种方式计算的值进行比较，那就很快乐了。
RK 算法的核心思路： 通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了。
来看一下 java.utils.String 中计算 hash 值是如何做的，

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }
​

它要遍历每个字符来计算 hash 值，虽然通过计算 hash 值提高了比较效率，但是计算 hash 值的代价也挺高呀，看起来效率也没提升呀，不急呀，这里就要设计其他的 hash 函数了。
要处理的字符串就只包含 a～z 这 26 个小写字母，那就用二十六进制来表示一个字符串。把 a～z 这 26 个字符映射到 0～25 这 26 个数字，a 就表示 0，b 就表示 1，以此类推，z 表示 25。来看一下十进制和二十六进制计算值的方式

那一个 m 长度的 adf...gaf 字符串的 hash 值就是

只要事先计算好这些 26^(m-1)的值，那就可以大幅度提高效率。

public static int rK(String mainStr, String matStr) {
        int m = mainStr.length(), n = matStr.length(), s, j;
        int[] hash = new int[m - n + 1];
        int[] table = new int[26];
        char[] a1 = mainStr.toCharArray();
        char[] b1 = matStr.toCharArray();
        s = 1;
        //将26的次方存储在一个表里，取的时候直接用
        for (j = 0; j < 26; j++) {
            table[j] = s;
            s *= 26;
        }
        for (int i = 0; i <= m - n; i++) {
            s = 0;
            for (j = 0; j < n; j++) {
                s += (a1[i + j] - 'a') * table[n - 1 - j];
            }
            hash[i] = s;
        }
        s = 0;
        for (j = 0; j < n; j++) {
            s += (b1[j] - 'a') * table[n - 1 - j];
        }
        for (j = 0; j < m - n + 1; j++) {
            if (hash[j] == s) {
                return j;
            }
        }
        return -1;
    }
​