串匹配三：Rabin-Karp指纹字符串查找算法

现在介绍一种基于散列的字符串匹配算法：
计算模式串的散列函数，然后用相同的散列函数计算文本中所有可能的M个字符的子字符串散列值并寻找匹配，找到之后，再继续验证2者是否匹配。

a.png

根据这段描述，直接实现的算法并不会比暴力查找快很多，因为计算散列值会涉及子字符串的每个字符，成本比直接比较这些字符要高很多。

Rabin和Karp发明了一种能够在常数时间内算出M个字符的子字符串散列值得方法，这样就得到了在时间运用中的运行时间为线性级别的子字符串查找算法。

• 散列函数

/* 计算txt[0...(m-1)] 的散列值 */
long hash(const string& txt, int m)
{
    long h = 0;
    for (int j = 0; j < m; j++)
        h = (R * h + txt[i]) % Q;
    return h;
}

这里用除留余数发计算散列值，所需时间与m成正比。

Rabin-Karp算法的基础是对所有位置i，高效计算文本中i+1位置的子字符串散列值，这可以由一个简单的数学公式得到，我们用ti表示txt[i]，那么文本txt中起始于位置i的含有M个字符的子字符所对应的数即为：

Rabin-Karp.png

public class RabinKarp {
    private String pat;     // 模式字符串(仅仅用于拉斯维加斯算法)
    private int M;          // 模式字符串的长度
    private long patHash;   // 模式字符串的散列值
    private long Q;         // 一个很大的素数
    private int R = 256;    // 字母表的大小
    private long RM;        // R^(M-1)
    
    public RabinKarp(String pat){
        this.pat = pat;
        this.M = pat.length();
        
        Q = longRandomPrime();
        
        RM = 1;
        for (int i = 1; i <= M-1; i++)
            RM = (R * RM) % Q;
        
        patHash = hash(pat, M);
    }
    
    public boolean check(int i) {
        return true;
    }
    
    /* 计算key[0, M-1]的散列值  */
    private long hash(String key, int M){
        long h = 0;
        for (int j = 0; j < M; j++)
            h = (R * h + key.charAt(j)) % Q;
        return h;
    }

    private int search(String txt){
        int N = txt.length();
        long txtHash = hash(txt, M);
    
        /* 一开始就匹配成功 */
        if (patHash == txtHash&&check(0))
            return 0;
        
        for (int i = M; i < N; i++) {
            txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q;
            txtHash = (txtHash*R + txt.charAt(i) % Q);
            
            if (patHash == txtHash) {
                if (check(i - M + 1))
                    return i - M + 1;
            }
        }
        return N;
    }
}