一、RK算法

RK 算法的全稱叫 Rabin-Karp 算法，是由它的兩位發(fā)明者 Rabin 和 Karp 的名字來命名的。

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

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

可以設(shè)計(jì)一個(gè)hash算法： 將字符串轉(zhuǎn)化成整數(shù)，利用K進(jìn)制的方式 數(shù)字1-0 ：

10進(jìn)制 123的拆解

100+20+3=123

小寫字母a-z：26進(jìn)制

大小寫字母a-Z:52進(jìn)制

大小寫字母+1-0:62進(jìn)制

以只是小寫字母的26進(jìn)制為例

字符串“abc”轉(zhuǎn)化成hash值的算法是：

a的ASCII碼是97

b的ASCII碼是98

c的ASCII碼是99

65572+2548+99=68219

字符串“abc”轉(zhuǎn)化成hash值是68219

如果覺得計(jì)算太麻煩也可以從97開始，

即 字符串“abc”轉(zhuǎn)化成hash值的算法是：

0+26+2=28 代碼如下：

/**
 * 字符串hash值匹配
 */
public class RKalth {
    public static boolean isMatch(String main, String sub) {
        //算出子串的hash值
        int hash_sub=strToHash(sub);
        for (int i = 0; i <= (main.length() - sub.length()); i++) {
        // 主串截串后與子串的hash值比較
            if (hash_sub==strToHash(main.substring(i, i + sub.length()))) {
                return true;
            }
        }
        return false;
    }
    /**
     * 支持 a-z 二十六進(jìn)制
     * 獲得字符串的hash值
     * @param src
     * @return
     */
    public static int strToHash(String src) {
        int hash = 0;
        for (int i = 0; i < src.length(); i++) {
            hash *= 26;
            hash += src.charAt(i) - 97;
        }
        return hash;
    }
    public static void main(String[] args) {
        System.out.println(isMatch("abcvdcd","vdcd"));
    }
}

時(shí)間復(fù)雜度

RK 算法的的時(shí)間復(fù)雜度為O(m+n)

m:為匹配串長度

n:為主串長度

應(yīng)用

適用于匹配串類型不多的情況，比如：字母、數(shù)字或字母加數(shù)字的組合 62 (大小寫字母+數(shù)字)