Module rabin_karp

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);

原理

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值

Structs

RabinKarp