Rabin

Rabin-Karp 优化算法

还可以叫 Karp-Rabin 优化算法，由 Richard M. Karp 和 Michael O. Rabin 在 1987 年发布，而且也是用于处理多模式串匹配问题的。它控制方式有点儿不同寻常，关键在于测算2个字符串数组的hash值，随后通过对比这俩hash值大小来确定是否发生配对。

2. 基本原理

Rabin-Karp 优化算法应用哈希函数进行计算字符串数组的hash值。哈希函数是一种将随意长度键入数据映射为固定不动长短输出函数公式。在 Rabin-Karp 优化算法中，使用哈希函数进行计算字符串数组的hash值，并较为如何在文字字符串数组中获得同样的hash值。

比如，假定我们有一个文字字符串数组 “hello world” 和一个方式字符串数组 “world”。我们可以用哈希函数进行计算这俩字符串数组的hash值。那这2个hash值相同，那我们就可以看作方式字符串数组在文字字符串数组中存在。

3. 完成

下边是一个应用 Rust 语言表达达到的 Rabin-Karp 优化算法实例：

fn rabin_karp(text: &str, pattern: &str) -> Vec<usize> {
    let n = text.len();
    let m = pattern.len();
    let base: u64 = 256;
    let modulus: u64 = 101;
    let mut res = Vec::new();

    if m > n {
        return res;
    }

    // Precompute (base ** (m - 1)) % modulus
    let mut h: u64 = 1;
    for _ in 0..m - 1 {
        h = (h * base) % modulus;
    }

    // Compute the hash value of pattern and first window of text
    let mut p: u64 = 0;
    let mut t: u64 = 0;
    for i in 0..m {
        p = (base * p   pattern.as_bytes()[i] as u64) % modulus;
        t = (base * t   text.as_bytes()[i] as u64) % modulus;
    }

    // Slide the pattern over text one by one
    for i in 0..n - m   1 {
        // Check the hash values of current window of text and pattern
        if p == t {
            // Check if the characters are actually the same
            if text[i..i   m] == *pattern {
                res.push(i);
            }
        }

        // Calculate the hash value for next window of text
        if i < n - m {
            t = (base * (t - text.as_bytes()[i] as u64 * h)   text.as_bytes()[i   m] as u64) % modulus;

            // We might get negative value of t, converting it to positive
            if t < 0 {
                t  = modulus;
            }
        }
    }

    res
}

上边的代码编写了 Rabin-Karp 优化算法。它最先计算模式字符串数组和文字字符串数组第一个窗口hash值，随后逐一滑动窗口并较为hash值。假如hash值相同，则进一步较为标识符是不是同样。假如标识符同样，则把所在位置导入到结论中。

复杂度分析：Rabin-Karp 算法算法复杂度为 O(n)，在其中 n 是文字字符串的长度。空间复杂度为 O(1)。

4. 运用

Rabin-Karp 优化算法主要是用于检验文章内容剽窃，例如 Semantic Scholar 的监测系统。它可以迅速地在文章中寻找原料里的语句，与此同时忽视例如英文大小写与标点符号等各个方面。

Rabin-Karp 优化算法具备一些优势，比如它可以迅速地检验文章内容剽窃，并且能解决海量数据。但它也有一些缺陷，比如它对哈希碰撞特别敏感，而且在最糟前提下算法复杂度会衰退为 O(nm)，在其中 n 是文字字符串的长度，m 是方式字符串的长度。

Rabin-Karp 优化算法是一种非常好用的字符串匹配优化算法，它能够迅速地处理多模式串匹配问题，而且具有较好的特性。from刘金，转载请注明原文链接。感激！