Rabin-Karp字符串匹配查找算法

https://www.cnblogs.com/ljc20020730/p/7285694.html

字符串x1,x2,x3……xk
基底e;模数mo;
hash=(xke^0+xk-1e^{1+......+x1*e}k-1)mod mo
注意：
①字符映射到数字不要映射到0
②基底e>字符种类数
③据说mo数为大素数出错概率小
mo=1000000007（存int64）
mo=666623333
递推建hash：
初始条件：hash[1]=x1;
递推式：hash[i]=(hash[i-1]*e+xi)mod mo;

区间hash：
对于任意关于x的子串xi-xj
hash[i,j]=(xje^0+xj+1e^{1+......+xi*e}j-i)mod mo;
O(n)的算法
hash[i,j]=(hash[j]-hash[i-1]*e^(j-i+1) mod mo+mo)mod mo
O(1)的算法

代码如下：
https://github.com/TheAlgorithms/Python/blob/master/strings/rabin_karp.py

# Numbers of alphabet which we call base
alphabet_size = 256
# Modulus to hash a string
modulus = 1000003


def rabin_karp(pattern, text):
    """
    The Rabin-Karp Algorithm for finding a pattern within a piece of text
    with complexity O(nm), most efficient when it is used with multiple patterns
    as it is able to check if any of a set of patterns match a section of text in o(1) given the precomputed hashes.
    This will be the simple version which only assumes one pattern is being searched for but it's not hard to modify
    1) Calculate pattern hash
    2) Step through the text one character at a time passing a window with the same length as the pattern
        calculating the hash of the text within the window compare it with the hash of the pattern. Only testing
        equality if the hashes match
    """
    p_len = len(pattern)
    t_len = len(text)
    if p_len > t_len:
        return False

    p_hash = 0
    text_hash = 0
    modulus_power = 1

    # Calculating the hash of pattern and substring of text
    for i in range(p_len):
        #计算patten字符串和文本的第一个pattern长度的字符串的 hash
        #其他帖子里说的预处理部分， 耗时O(m)的部分
        p_hash = (ord(pattern[i]) + p_hash * alphabet_size) % modulus
        text_hash = (ord(text[i]) + text_hash * alphabet_size) % modulus
        if i == p_len - 1:
            continue
        modulus_power = (modulus_power * alphabet_size) % modulus

    for i in range(0, t_len - p_len + 1):
        if text_hash == p_hash and text[i : i + p_len] == pattern:
            return True
        if i == t_len - p_len:
            continue
        # Calculating the ruling hash
        #这里使用到了O(1)计算的过程，用之前窗口的hash值减去字符串第一个字符贡献的hash之部分，再加上新的一位字符的hash值。
        text_hash = (
            (text_hash - ord(text[i]) * modulus_power) * alphabet_size
            + ord(text[i + p_len])
        ) % modulus
    return False


def test_rabin_karp():
    """
    >>> test_rabin_karp()
    Success.
    """
    # Test 1)
    pattern = "abc1abc12"
    text1 = "alskfjaldsabc1abc1abc12k23adsfabcabc"
    text2 = "alskfjaldsk23adsfabcabc"
    assert rabin_karp(pattern, text1) and not rabin_karp(pattern, text2)

    # Test 2)
    pattern = "ABABX"
    text = "ABABZABABYABABX"
    assert rabin_karp(pattern, text)

    # Test 3)
    pattern = "AAAB"
    text = "ABAAAAAB"
    assert rabin_karp(pattern, text)

    # Test 4)
    pattern = "abcdabcy"
    text = "abcxabcdabxabcdabcdabcy"
    assert rabin_karp(pattern, text)

    # Test 5)
    pattern = "Lü"
    text = "Lüsai"
    assert rabin_karp(pattern, text)
    pattern = "Lue"
    assert not rabin_karp(pattern, text)
    print("Success.")


if __name__ == "__main__":
    test_rabin_karp()

网上的帖子有很多，大致看完之后，本人倾向于下面帖子的分析：
https://blog.csdn.net/lucylove3943/article/details/83491416

Rabin-Karp是用来解决字符串匹配（查重）的问题的。该问题的严谨定义如下：
Input：一段字符串t，和一个字符串p
Output：如果t中含有p，那么输出yes，如果没有，输出no
看p是不是t的子字符串，如果是的话，输出yes，如果不是的话，输出no。
Michael O. Rabin和Richard M. Karp在1987年提出一个想法，即可以对模式串进行哈希运算并将其哈希值与文本中子串的哈希值进行比对。总的来说这一想法非常浅显，唯一的问题在于我们需要找到一个哈希函数 ，它需要能够对不同的字符串返回不同的哈希值。例如，该哈希函数可能会对每个字符的ASCII码进行算，

如何hashing字符串
比较笼统和宽泛的来说，哈希其实就是把一个定义域较宽的集合映射到一个值域较小的集合。一般来说，我们映射的结果是一个整数，也就是俗称的地址。比如说现在有一个数为x，我们希望进行哈希运算之后的H(x)是一个整数，然后我们把x放到哈希表中地址为H(x)的地方。
如果x是一个数字，这个理解起来比较直观，我们可以定义哈希函数为对这个数字的四则运算，得到一个新的数字，作为x的哈希值。
那么如果x是一个字符串S呢？如果通过一个哈希函数，把字符串S转换为一个整数呢？Hashing字符串一般用的是如下公式：

image.png

其中，代表的是S的定义域大小，比如说如果S全是英文字母，那么的值为26，因为英文字母就只有26个。然后这个函数是一个映射函数，映射S的定义域中的每一个字符到数字的函数。
根据上面的这个公式，就能把任意一个字符串S映射为一个整数。
Brute Force算法（暴力解法）
暴力破解Substring Pattern Matching的方法十分直观，过程如下：
假设字符串t的长度为n，字符串p的长度为m。
在字符串t上，放一个长度为m窗口window。
从头开始慢慢的滑动这个窗口window，每滑动一次，就把窗口里的内容和p对比一下。
如果一样，就返回yes。如果不一样，那么继续往右滑动一格窗口window。
从上述算法可知，in worst case，一共会有(n-m+1)个窗口滑动。->这一步的复杂度是O(n)
然后每次窗口滑动，都涉及到两个长度为m的字符串的比较。->这一步的复杂度是O(m)
由于这两部是一个nested loop，所以最终的算法复杂度是O(m*n)。

Rabin-Karp算法
基本思想和暴力破解算法是一样的。也需要一个大小为m的窗口，但是不一样的是，不是直接比较两个长度为m的字符串，而是比较他们的哈希值。
同样的，现在我们做他们的复杂度分析，in worst case，一共会有(n-m+1)个窗口滑动。->这一步的复杂度是O(n)
这个是不变的，但是由于哈希值都是数字，所以两个数字的比较，只需要O(1)。
但是计算哈希值的时间呢？
在一开始的时候，我们需要计算p的哈希值，由于p的长度为m，所以计算p的哈希值的时间为O(m).
然后每一次移动窗口，都需要对窗口内的字符串计算哈希值，此时这个字符串的长度为m，所以计算它哈希值的时间也为O(m).如果照这样看，算法复杂度还是O(m+n)，和上面的暴力破解算法没有任何区别。
但是实际上，计算移动窗口内的哈希值并不需要O(m)，在已知前一个窗口的哈希值的情况下，计算当前窗口的哈希值，只需要O(1)的时间复杂度。
现在再来看上面提到的计算字符串哈希值的函数，假设现在窗口的起点在j这个位置，此时窗口内的字符串哈希值为：

image.png
那么，当计算下一个窗口的哈希值时，也就是当窗口的起点为j+1时，哈希函数值可由如下方法计算：
image.png
所以，这样看来，在计算出第一个窗口的函数值之后，后面的每一个窗口哈希值都可以根据上述公式计算，只需要做一次减法，一次乘法，一次加法。所以之后的每一次哈希值计算都是O(1)的复杂度。

那么重头来算一次复杂度：
一共有(n-m+1)个窗口，复杂度为O(n).
计算p的哈希值O(m)，计算第一个窗口的复杂度，O(m).
此后计算每一个窗口的复杂度O(1).
所以最终的复杂度是O(m+n)。

参考资料：
https://blog.csdn.net/woshinannan741/article/details/50372598

https://blog.csdn.net/lucylove3943/article/details/83491416

https://blog.csdn.net/m0_37846371/article/details/72854890

https://blog.csdn.net/tyler_download/article/details/52457108

自己的总结：
对字符进行编码，不同的字符对应不同的整数数值，选取一个基数N（类似16进制的16），基数>字符种类数，类比于16进制数一样，每个字符对应一个N进制数，且各不相同，然后将长度为M的pattern字符串看作一个M位的N进制数，Hash函数就是计算这个M位N进制数的 数值。那么不同的pattern字符串一定是对应不同的数值
然后对长度位K的文本，从位置0开始，每次滑动1个位置，计算K-M+1次窗口大小为M的字符串的hash值，与pattern的hash值做比对即可。

为什么有概率比对不上？
做个极限假设，假如N很大，M也较大（匹配字符串较长），那么pattern的hash值-P0和每次滑动比对窗口的M位字符串对应的hash-P1就有可能是一个很大的数值，大到int或者longint 32bit/64bit数值表示不了（会溢出），假设int型表示hash值，那么就会出现P1 = P0 + K*2^32 (K为整数)的情况，即P0-P1 同余的情况（这里模数相当于是2^32），所以模数mo选择越大，出错概率越小，并不是什么玄学，因为溢出的概率越小。