字符串匹配算法之BF算法和RK算法

BF算法

俗称暴力破解法，假设有长度为m的子串，长度为n的主串, n>=m， 那么BF算法的思想就是每轮遍历m个字符，遍历n-m+1次，最坏的时间复杂度为O(n*m)。

RK算法

比较子串的hash值与带比较串的hash是否相等，一直则说明存在。时间复杂度O(n)

# RK算法

HEX = 61


def compute_hash(child: str, lens: int) -> int:
    """
    计算子串hash
    """
    res = 0
    for i in range(len(child)-1, -1, -1):
        res += ord(child[i]) * (HEX**(lens-i-1))
    return res


def rk(main: str,  child: str) -> bool:
    """ 
    RK算法
    假设要比较的字符只在大写/小写字母、数字中
    时间复杂度O(n)
    """
    n = len(main)
    m = len(child)
    first = compute_hash(child, m)
    # 边计算边存储
    h = [0 for _ in range(n-m+1)]
    h[0] = compute_hash(main[0:m], m)
    if h[0] == first:
        return True
    # 遍历一轮，动态根据h[i-1]计算h[i]的hash值
    for i in range(1, n-m+1):
        h[i] = (h[i-1] - (HEX**(m-1))*ord(main[i-1]))*HEX + ord(main[i+m-1])
        if first == h[i]:
            return True
    return False


res = rk('abcd', 'bcd')
print(res)