字符串匹配1：BF算法和RK算法

字符串匹配可分为单模式串匹配和多模式串匹配，单模式串匹配就是一个串和一个子串匹配，多模式串匹配可以一个串同时查找多个字串。

为了更好的实现字符串匹配算法，定义接口如下：

/**  
 * 匹配器  
 */  
public interface Matcher {  
  
    /**  
     * 是否有匹配的串  
     * @param source  
     * @param word  
     * @return  
     */  
    boolean match(CharSequence source,CharSequence word);  
  
    /**  
     * 获取匹配串的index  
     * @param source  
     * @param word  
     * @return  
     */  
    int find(CharSequence source,CharSequence word);  
  
}

BF算法

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法，它是一种单模式串匹配算法。

BF算法的思路非常简单，假设有一个主串和一个子串，子串从index=0开始匹配，逐个字匹配，如果匹配失败则从index=1重新开始匹配，依此类推，匹配失败字串就向后移动一位。

[abcd]  ——>  [abcd]  -->  [abcd]
[cd]          [cd]          [cd]

极端情况出现在这样的情况下，主串类似"aaaaaa……aaaaab"，字串aaaab这样的情况下。我们每次都要对比m次，要匹配n-m+1次，m是字串长度，n是主串长度。时间复杂度是O(n×m)。

package cn.lishiyuan.algorithm.strings;  
  
/**  
 * 暴力匹配算法  
 */  
public class BFMatcher implements Matcher{  
  
    @Override  
    public boolean match(CharSequence source, CharSequence word) {  
        return find(source,word) != -1;  
    }  
  
    @Override  
    public int find(CharSequence source, CharSequence word) {  
        // codePoints或者chars  
        int[] sourceArray = source.chars().toArray();  
        int[] wordsArray = word.chars().toArray();  
  
        if (sourceArray.length < wordsArray.length){  
            return -1;  
        }  
          
        if (wordsArray.length == 0){  
            return -1;  
        }  
  
        int index = -1;  
  
        for (int i = 0; i < (sourceArray.length - wordsArray.length + 1); i++) {  
            // 逐字匹配  
            boolean match = true;  
            for (int j = 0; j < wordsArray.length; j++) {  
                if(sourceArray[i+j] != wordsArray[j]){  
                    match = false;  
                    break;                }  
            }  
            // 已匹配  
            if(match){  
                index = i;  
                break;            }  
        }  
  
        return index;  
    }  
}

暴力匹配算法的思路和实现都非常简单，效率虽然不高但是在实际生产中可以优先使用，毕竟实际生产中很难有超长串匹配的时候。当然，通常我们都会使用现成库。

RK算法

RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。它是一种单模式串匹配算法。

RK算法的思想是对目标串和同长度子串进行哈希，如果哈希值相同，则表示两个串是匹配的。当然这是理想状态，一方面，哈希值相同，不一定就是匹配的，另一方面，如果每次都对整个子串进行哈希，那么其效率并不会比BF算法高。

对于第一个问题，有两个处理方法，一是使两个hash函数获取两个不同的哈希值，降低哈希冲突；二是在哈希值一致是进行逐字匹配；对于第二种情况，需要设计合适的hash算法，使得当前子串的哈希值与前一个子串的哈希值关联，使得不用每次全部计算哈希值。

假设主串是：abcdef ；目标串是：cdef。

则目标串计算哈希值计算如下

h = c × (base ^ 0) + d × (base ^ 1) + e × (base ^ 2) + f × (base ^ 3)

字串哈希值计算如下

h1 = a × (base ^ 0) + b × (base ^ 1) + c × (base ^ 2) + d × (base ^ 3) 

h2 = b × (base ^ 0) + c × (base ^ 1) + d × (base ^ 2) + e × (base ^ 3)

h2 = (h1 - a ) / base + e × base ^ 3

但是，在长串的时候，hash值很容易溢出，所以我们要在每一步运算之后都做取模运算，防止hash值溢出数据类型的最大值。

package cn.lishiyuan.algorithm.strings;  
  
/**  
 * Rabin-Karp 算法  
 */  
public class BKMatcher implements Matcher{  
  
    private long base = 257;  
  
    private long mod = 1000000007;  
  
    @Override  
    public boolean match(CharSequence source, CharSequence word) {  
        return find(source,word) != -1;  
    }  
  
    @Override  
    public int find(CharSequence source, CharSequence word) {  
  
        // codePoints或者chars  
        int[] sourceArray = source.chars().toArray();  
        int[] wordsArray = word.chars().toArray();  
  
        int wordsArrayLength = wordsArray.length;  
        int sourceArrayLength = sourceArray.length;  
  
        if (sourceArrayLength < wordsArrayLength){  
            return -1;  
        }  
  
        if (wordsArrayLength == 0){  
            return -1;  
        }  
  
        int index = -1;  
        long[] pow = basePow(wordsArrayLength-1);  
        long wordHash = hash(wordsArray,0,wordsArrayLength,0,pow);  
        long oldHash = 0;  
  
        for (int i = 0; i < sourceArrayLength - wordsArrayLength + 1; i++){  
  
            // 循环  
            long hash = hash(sourceArray,i,wordsArrayLength,oldHash,pow);  
            if (wordHash == hash){  
                boolean match = true;  
                for (int j = 0; j < wordsArrayLength; j++) {  
                    if (wordsArray[j] != sourceArray[i+j]){  
                        match = false;  
                        break;                    }  
                }  
                if(match){  
                    index = i;  
                    break;                }  
            }  
  
            oldHash = hash;  
        }  
  
        return index;  
    }  
  
    private long[] basePow(int n){  
        long[] pow = new long[n + 1];  
        pow[0] = 1;  
        for (int i = 1; i <= n; i++) {  
            // 每一步都取模防止溢出  
            pow[i] = (pow[i - 1] * base) % mod; // 预计算模mod的幂次  
        }  
        return pow;  
    }  
  
  
    // 滚动hash  
    private long hash(int[] arr, int start, int length, long hash, long[] pow) {  
        // 初始化时计算哈希  
        if (hash == 0) {  
            long h = 0;  
            for (int i = 0; i < length; i++) {  
                // 每一步都取模防止溢出  
                h = (h + (long) arr[start + i] * pow[length - 1 - i]) % mod; // 权重从高位到低位  
            }  
            return h;  
        } else {  
            // 移除首字符影响，添加新字符  
            // 每一步都取模防止溢出  
            long remove = (arr[start - 1] * pow[length - 1]) % mod;  
            long add = arr[start + length - 1] % mod;  
            hash = (hash - remove) % mod;  
            hash = (hash * base + add) % mod;  
  
            return hash < 0 ? hash + mod : hash; // 确保非负  
        }  
    }  
  
}

这里，我们使用一个底257进行幂运算，并且通过basePow得到每一位的基础幂值。在我们具体计算hash值的时候不用重新运算。我们每一步都进行模运算，防止数据溢出。

值得注意的是hash < 0 ? hash + mod : hash;这一步保证了Java程序运算与数学运算一致。比如-7 % 3在java运算中结果是-1，符号未参与，直接保留了下来，而在数学定义上，取模运算的结果是一个[0,mod)区间的数，不存在负数，数学上-7 % 3的结果是2。

hash值为负数的时候会出现在hash - remove的时候，删除了一个大于当前hash值的数。

注：模运算的代数性质（运算后取模和取模运算后再取模的结果是相同的）

加法：(a+b) mod p =[(a mod p) + (b mod p)] mod p
减法：(a−b) mod p=[(a mod p) − (b mod p) + p] mod p（加 p 避免负数结果）
乘法：(a×b) mod p=[(a mod p)× (b mod p)] mod p

字符串匹配1：BF算法和RK算法

BF算法

RK算法

评论已关闭

最新文章

分类