Rust字符串匹配Rabin-Karp算法詳解

更新時間：2023年05月21日 10:40:17 作者：Pomelo_劉金

Rabin-Karp算法也可以叫 Karp-Rabin 算法，它是用來解決多模式串匹配問題的，它的實現(xiàn)方式有點與眾不同，首先是計算兩個字符串的哈希值，然后通過比較這兩個哈希值的大小來判斷是否出現(xiàn)匹配，本文詳細介紹了字符串匹配Rabin-Karp算法,需要的朋友可以參考下

1. Rabin-Karp 算法

也可以叫 Karp-Rabin 算法，由 Richard M. Karp 和 Michael O. Rabin 在 1987 年發(fā)表，它也是用來解決多模式串匹配問題的。它的實現(xiàn)方式有點與眾不同，首先是計算兩個字符串的哈希值，然后通過比較這兩個哈希值的大小來判斷是否出現(xiàn)匹配。

2. 原理

Rabin-Karp 算法使用哈希函數(shù)來計算字符串的哈希值。哈希函數(shù)是一種將任意長度的輸入數(shù)據(jù)映射為固定長度輸出的函數(shù)。在 Rabin-Karp 算法中，我們使用哈希函數(shù)來計算字符串的哈希值，并比較能否在文本字符串中得到相同的哈希值。

例如，假設我們有一個文本字符串 “hello world” 和一個模式字符串 “world”。我們可以使用哈希函數(shù)來計算這兩個字符串的哈希值。如果這兩個哈希值相等，那么我們就可以認為模式字符串在文本字符串中出現(xiàn)了。

3. 實現(xiàn)

下面是一個使用 Rust 語言實現(xiàn)的 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
}

上面的代碼實現(xiàn)了 Rabin-Karp 算法。它首先計算模式字符串和文本字符串第一個窗口的哈希值，然后逐個滑動窗口并比較哈希值。如果哈希值相等，則進一步比較字符是否相同。如果字符相同，則將當前位置添加到結(jié)果中。

復雜度分析：Rabin-Karp 算法的時間復雜度為 O(n)，其中 n 是文本字符串的長度。空間復雜度為 O(1)。