【笔记】字符串匹配基础入门

hack_hu

BF 暴力匹配法

BF(Brute - Force) 暴力匹配算法，是字符串匹配算法中最基础，也是最常用的算法。

BF算法，即暴风(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法.

在字符串匹配中，将源字符串称之为 主串 ，需要匹配的子串称之为 模式串 。

例：在 source 字符串的子串中查找是否有 target 字符串一样的。 source 就是 主串，target 就是 模式串。

而任意 m 大小的主串，只有 m-n+1 个大小为 n 的子串。（注：这里的子串并非是指主串中的元素组合、而是指主串中连续的某一段）
参考代码

// source 是主字符串、target 是要匹配的模式串
    public boolean bruteForce(String source, String target) {
        // BF 字符串暴力匹配算法，从源字符串的第 1 个字母开始和 target1 首字母比较，若相等则依次向后比较
        // 不相等则再寻找下 1 相同字母索引
        boolean result = false;
        int len = source.length() - target.length()+1; // 最多需要比较的次数
        int subStrLen = target.length();
        for (int i = 0; i < len; i++) {
            if (source.charAt(i) == target.charAt(0)) {
                result = source.substring(i, i + subStrLen).contentEquals(target);
                if (result == true)
                    return true; // 当出现相等模式串时返回 true
            }
        }
        return false;
    }

思路：遍历主串，在找到第 1 个与模式串首字母相同的字符时，开始匹配，若不一致，则在主串中寻找下一个匹配字符。

从算法的时间复杂度来看 BF 暴力匹配算法 的时间复杂度是 O( M*N )，M 为主串长度，N 为模式串长度。属于复杂度比较高的算法，但是因为写法简单，不宜出错，所以最为常用，后续的 所有的字符串匹配算法其实就是对 BF 算法的优化。

RK 算法

RK 算法全名为：Rabin-Karp，由两位创始人的名字组成

思路：把主串中的 M-N+1 个子串生成哈希值，再让模式串生成哈希值，当子串和模式串生成的哈希值一致时，我们再比较子串和模式串是否一致（存在哈希冲突的可能性），一致则匹配成功，不一致则继续在子串中查找。

    public boolean RK(String source,String target) {
        int len = source.length()-target.length()+1;
        int tarLen= target.length();
        int targetValue=hashValue(target);
        String tempStr;
        for(int i=0;i<len;i++)
        {
            tempStr=source.substring(i,i+tarLen);
            // 注意字符串不能直接用 == 比较，因为 == 比较的是两个字符串是否引用同一对象
            if(hashValue(tempStr)==targetValue&&tempStr.contentEquals(target)) 
                return true;
        }
        return false;
    }
    public int hashValue(String str) { // 哈希函数
        int value=0;
        int len = str.length();
        for(int i=0;i<len;i++)
        {
            value+=str.charAt(i)-'a'; // 假设所有的字符都是小写英文字母
        }
        return value;
    }

总结，借助哈希算法的思想，RK 算法的时间复杂度大致为 O(M)，M 为主串的长度。但是因为字符串可能为不同的类型（字符大小写、数值），这会增加哈希函数的复杂度，但是总体来说 RK 算法 的效率比 BF 算法 的效率更高。

回顾一下散列表的知识点。哈希函数的设计主要还是采用了「除留余数法」，将各种类型先转换成整数再放入散列数组。