RK算法的时间复杂度和空间复杂度

RK算法是一种字符串匹配算法，其时间复杂度为O(n+m)，其中n为主串长度，m为模式串长度。空间复杂度为O(1)，因为该算法只需要常数级别的额外空间来存储hash值和比较结果。具体实现可以参考以下代码：

def RK_match(s, p):
    n, m = len(s), len(p)
    if n < m:
        return -1
    # 计算模式串的hash值和主串中第一个子串的hash值
    base, mod = 31, 10**9+9
    p_hash, s_hash = 0, 0
    for i in range(m):
        p_hash = (p_hash*base + ord(p[i])) % mod
        s_hash = (s_hash*base + ord(s[i])) % mod
    # 滑动窗口匹配
    for i in range(n-m+1):
        if p_hash == s_hash and s[i:i+m] == p:
            return i
        if i < n-m:
            s_hash = (s_hash - ord(s[i])*pow(base, m-1, mod)) % mod
            s_hash = (s_hash*base + ord(s[i+m])) % mod
    return -1