algorithms_fourth 0.1.10

//! Rabin-Karp 指纹字符串查找算法
//!
//! # 使用
//! ```
//!         use algorithms_fourth::search::rabin_karp::RabinKarp;
//!         let kmp = RabinKarp::new("abc".to_string());
//!         assert_eq!(kmp.search("ababac"), 6);
//!         assert_eq!(kmp.search("ababcc"), 2);
//!         assert_eq!(kmp.search("ababccababcc"), 2);
//!         assert_eq!(kmp.search("abcbcc"), 0);
//!         assert_eq!(kmp.search("babcbcc"), 1);
//!         assert_eq!(kmp.search("aabcbcc"), 1);
//!         assert_eq!(kmp.search("ab"), 2);
//!
//! ```
//!
//! # 原理
//! <pre>
//! 1. 字符串匹配的耗时在于字符串的长度，一个一个字符匹配可能伴随着一次不匹配的出现
//! 是基于很多个字符的已经匹配。
//! 2. 在思考1的时候，会很希望模式字符串的长度只有1，如此1中的耗时也就不存在了。而数字
//! 是高效匹配的理想类型。
//! 3. 基于想法2，可以找到一个高效将字符串转为数字的算法，假设模式长度为m，待检测字符串的长度为n，
//! 则只需要匹配n-m+1次即可。
//!     3.1. 分析数字，进制位其实就是长度转化的结果
//!     3.2. 等价代入，设字符串为R位进制，模式长度为m，txt中0位自字符为h，m位字符为l，
//!     假设txt[0..m]的数值是v，则 txt[1..m+1] =  (v - (R^(m-1) * h) )*R   +  l .
//!     假设RM = R^(m-1),上边简化为:txt[1..m+1] =  (v - (RM * h) )*R  +  l .
//!     3.2. 数字必然对应着越界，为了防止越界就需要取余，取余就要考虑多对一问题，所以用适当大的质数
//!     来做因数，假设为Q，来尽可能地减少多对一的情况。
//!     3.3. 加入了取余操作，则必须考虑负数情况。为了避免负数情况，需要先加Q来保证减法时一定为正，
//!     然后再用取余去去除可能多出来的Q。所以3.2的公式变为:
//!     txt[1..m+1] =  ( (v+Q-(RM * h)%Q )%Q*R  +  l ) %Q.
//!     3.4. 信息数字化的思想通常称之为hash，所以txt[1..m+1]也成为hash值
//! </pre>

const R: usize = 256;
pub struct RabinKarp {
    pat: String,
    pat_hash: usize,
    m: usize,
    q: usize,
    rm: usize,
}
impl RabinKarp {
    pub fn new(pat: String) -> Self {
        let m = pat.len();
        let q = long_prandom_prim();
        let mut rm = 1;
        for _ in 1..m {
            rm = (R * rm) % q;
        }
        let pat_hash = hash(q, &pat, m);
        RabinKarp {
            pat,
            pat_hash,
            m,
            q,
            rm,
        }
    }
    pub fn search(&self, txt: &str) -> usize {
        let n = txt.len();
        if n < self.pat.len() {
            return txt.len();
        }
        let mut txt_hash = hash(self.q, txt, self.m);
        if self.pat_hash == txt_hash && self.check(txt, 0) {
            0
        } else {
            for i in self.m..n {
                //     txt[1..m+1] =  ( (v+Q-(RM * h)%Q )%Q*R +  l ) %Q.
                txt_hash =
                    (txt_hash + self.q - self.rm * char_at(txt, i - self.m) % self.q) % self.q;
                txt_hash = (txt_hash * R + char_at(txt, i)) % self.q;
                let t = i - self.m + 1;
                if self.pat_hash == txt_hash && self.check(txt, t) {
                    return t;
                }
            }
            n
        }
    }

    fn check(&self, txt: &str, start: usize) -> bool {
        (0..self.pat.len()).all(|i| -> bool { char_at(txt, i + start) == char_at(&self.pat, i) })
    }
}

fn char_at(txt: &str, i: usize) -> usize {
    txt.as_bytes()[i] as usize
}

fn hash(q: usize, pat: &str, m: usize) -> usize {
    let mut h = 0;
    for j in 0..m {
        h = (R * h + char_at(pat, j)) % q;
    }
    h
}

fn long_prandom_prim() -> usize {
    100000073
}

#[cfg(test)]
mod test {
    use crate::search::rabin_karp::RabinKarp;
    #[test]
    fn test() {
        let kmp = RabinKarp::new("abc".to_string());
        assert_eq!(kmp.search("ababac"), 6);
        assert_eq!(kmp.search("ababcc"), 2);
        assert_eq!(kmp.search("ababccababcc"), 2);
        assert_eq!(kmp.search("abcbcc"), 0);
        assert_eq!(kmp.search("babcbcc"), 1);
        assert_eq!(kmp.search("aabcbcc"), 1);
        assert_eq!(kmp.search("ab"), 2);
    }
}