Python中如何实现Rabin-Karp字符串匹配算法

2023-04-17 00:00:00 python 如何实现 Rabin

Rabin-Karp算法是一种快速的字符串匹配算法，其基本思想是通过哈希函数快速比较字符串的值是否相同，从而减少比较的次数。具体实现如下：

  1. 对模式串进行哈希处理：将模式串中每个字符的ASCII码值视为数字，然后通过给定的哈希函数计算它们的值，并将这些值组合成一个整数作为模式串的哈希值。

  2. 对主串中长度为模式串长度的子串进行哈希处理，并将它们与模式串的哈希值进行比较。如果相等，则说明该子串与模式串匹配。

  3. 如果两个哈希值不相等，则说明两个字符串不匹配。此时需要将哈希函数应用到下一个子串，并继续比较。

代码演示如下：

def rabin_karp(text, pattern):
    # 计算模式串的哈希值
    m, n = len(text), len(pattern)
    hpattern = sum(ord(pattern[i])*(10**(n-i-1)) for i in range(n))

    # 计算主串中每个长度为模式串长度的子串的哈希值
    htext = [0]*(m-n+1)
    htext[0] = sum(ord(text[i])*(10**(n-i-1)) for i in range(n))
    for i in range(1, m-n+1):
        htext[i] = 10*(htext[i-1]-ord(text[i-1])*(10**(n-1)))+ord(text[i+n-1])

    # 比较哈希值
    result = []
    for i in range(m-n+1):
        if hpattern == htext[i]:
            if pattern == text[i:i+n]:
                result.append(i)
    return result

使用样例：

text = "pidancode.com is a coding website"
pattern = "coding"
result = rabin_karp(text, pattern)
print(result) # 输出: [13]

以上代码实现了Rabin-Karp字符串匹配算法的基本思路，在实际应用中还需要考虑哈希函数的设计、哈希冲突的解决等问题，以提高算法的效率和准确性。

相关文章