14.字符串匹配算法

1.BF算法

1.1 定义

BF(Brute Force)算法,中文叫作暴力匹配算法，也叫朴素匹配算法。
思想:在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

image.png

1.2 性能分析

算法的最坏情况下的时间复杂度为O(n*m)。

1.3 实际场景

在实际的开发中，是一个比较常用的字符串匹配算法：
第一，实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。
第二，朴素字符串匹配算法思想简单，代码实现也非常简单。简单意味着不容易出错，如果有 bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。这也是我们常说的KISS（Keep it Simple and Stupid）设计原则。

1.4代码实现

     /**
     * BK实现的字符串匹配，返回符合的下标，不存在则返回-1
     * @param strMaster 主串
     * @param strSlave  模式串
     * @return
     */
    public static int indexOf(String strMaster, String strSlave) {
        // 校验
        if (strMaster == null || strSlave == null || strMaster.length() < strSlave.length()) {
            return -1;
        }
        int n = strMaster.length();
        int m = strSlave.length();
        //对于主串长度为n，子串长度为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;
                }
            }
            // 找到符合的匹配字符串的标志
            if (j == m ) {
                return i;
            }
        }
        return -1;
    }

RK算法

1.定义

BF算法:每次检查主串与子串是否匹配，需要依次比对每个字符，所以 BF 算法的时间复杂度就比较高，是 O(n*m)。我们对朴素的字符串匹配算法稍加改造，引入哈希算法，时间复杂度立刻就会降低。

RK算法思想:我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。

设计哈希函数

通过哈希算法计算子串的哈希值的时候，我们需要遍历子串中的每个字符。尽管模式串与子串比较的效率提高了，但是整体的算法效率并没有提高；
涉及思路:

我们假设要匹配的字符串的字符集中只包含 K 个字符，我们可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。

三个tips:

比如要处理的字符串只包含 a～z 这 26 个小写字母，那我们就用二十六进制来表示一个字符串。我们把 a～z 这 26 个字符映射到 0～25 这 26 个数字，a 就表示 0，b 就表示 1，以此类推，z 表示 25。

image.png
这种哈希算法有一个特点，在主串中，相邻两个子串的哈希值的计算公式有一定关系.
相邻两个子串 s[i-1]和 s[i]（i 表示子串在主串中的起始位置，子串的长度都为 m），对应的哈希值计算公式有交集，也就是说，我们可以使用 s[i-1]的哈希值很快的计算出 s[i]的哈希值:

image.png
那就是 26^(m-1) 这部分的计算，我们可以通过查表的方法来提高效率。我们事先计算好 26^0、261、26^2……26(m-1)，并且存储在一个长度为 m 的数组中，公式中的“次方”就对应数组的下标。当我们需要计算 26 的 x 次方的时候，就可以从数组的下标为 x 的位置取值，直接使用，省去了计算的时间。

2.实现

public static int rk(String strMas, String strSla) {
        // 健壮性判断(略过)
        // 主串的长度及对应的字符数组
        int n = strMas.length();
        char[] charMas = strMas.toCharArray();
        // 模式串的长度及对应的字符数组
        int m = strSla.length();
        char[] charSla = strSla.toCharArray();
        // 新建长度为26的数组，存储进制，会溢出，但是也没有问题，使用进制的目的就是保证不会重复
        int[] table = new int[26];
        table[0] = 1;
        for (int i = 1; i < 26; i++) {
            table[i] = table[i - 1] * 26;
        }
        // 新建数组，存储主串需要比较的n-m+1个子串的哈希值
        int[] hash = new int[n - m + 1];
        // 先计算出第一个子串的哈希值，从[0,m-1],table表示位数，最高位为[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');
        }
        // 计算模式串的哈希值
        int hashSla = 0;
        for (int i = 0; i <= m - 1; i++) {
            hashSla = hashSla + (charSla[i] - 'a') * table[m - 1 - i];
        }
        // 前戏准备完成，开始比较
        for (int i = 0; i < n - m + 1; i++) {
            if (hash[i] == hashSla) {
                return i;
            }
        }
        return -1;
    }

3.复杂度分析

整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。
对于计算子串哈希值可以通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 O(n)。
模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以，这部分的时间复杂度也是 O(n)。
所以，RK 算法整体的时间复杂度就是 O(n)。

4.改进

模式串很长，相应的主串中的子串也会很长，通过上面的哈希算法计算得到的哈希值就可能很大，如果超过了计算机中整型数据可以表示的范围，那该如何解决呢？

在之前设计的哈希算法是没有散列冲突的，也就是说，一个字符串与一个二十六进制数一一对应，不同的字符串的哈希值肯定不一样。因为我们是基于进制来表示一个字符串的。

方案:

重新设计哈希算法
对于哈希值不一致的，字符串肯定不一样，直接跳过；
对于哈希值一样的，再进行比较一次确定；
所有对于哈希函数的设计很有讲究，如果哈希冲突太多，RK算法在极端情况下会退化为BK算法。