2

我构建了一个函数，它基于 Rabin–Karp 算法按升序查找两个文本文件的最长公共子字符串。主要功能是“find_longest”，内部功能是：“make_hashtable”、“extend_fingerprints”和“has_match”。我无法分析has_match的平均案例复杂度。

将 n1,n2 表示为 text1,text2，将 l 表示为当前“窗口”的大小。finger 是子串的哈希表。

def has_match(text1,text2,fingers1,fingers2,l,r):
h = make_hashtable(fingers2,r)
for i in range(len(fingers1)):
    for j in h[fingers1[i]]:
        if text1[i:i+l] == text2[j:j+l]:
            return text1[i:i+l]
return None

这是“make_hashtable”，在这里我很确定复杂度是 O(n2-l+1)：

def make_hashtable(fingers, table_size):
hash_table=[[] for i in range(table_size)]
count=0
for f in fingers:
    hash_table[f].append(count)
    count+=1
return hash_table

这是“find_longest”，我添加了这个函数，尽管我不需要它来进行复杂性分析。

def find_longest(text1,text2,basis=2**8,r=2**17-1):
match = ''
l = 0 #initial "window" size
#fingerprints of "windows" of size 0 - all are 0
fingers1 = [0]*(len(text1)+1)
fingers2 = [0]*(len(text2)+1)

while match != None: #there was a common substring of len l
    l += 1
    extend_fingerprints(text1, fingers1, l, basis, r)
    extend_fingerprints(text2, fingers2, l, basis, r)
    match = has_match(text1,text2,fingers1,fingers2,l,r)
    print(match)
return l-1

这是“extend_fingerprints”：

def extend_fingerprints(text, fingers, length, basis=2**8, r=2**17-1):
count=0
for f in fingers:
    if count==len(fingers)-1:
        fingers.pop(len(fingers)-1)
        break
    fingers[count]=(f*basis+ord(text[length-1+count]))%r
    count+=1

我对这两个选项有疑问：

1.O(n_2-l+1)+O(n_1-l+1)*O(l) 将 r 称为常数，而 n1,n2 非常大，因此在哈希表中会发生很多冲突（假设每个“单元格”的 O(1) 项，但是，总是有一些“误报” ")

2.O(n_2-l+1)+O(n_1-l+1)+O(l)
将 r 称为最佳哈希函数，因此几乎没有冲突，这意味着如果两个文本是哈希表中的相同单元格，我们可以假设它们实际上是相同的文本？

我个人倾向于 Bold 声明。tnx。

4

1 回答 1

1

我认为答案是

O((n_2-l) + l*(n_1-l))

. (n_2-l) 表示第二个文本的 make_hashtable 的复杂度。l*(n_1-l) 表示两个嵌套循环，它们遍历第一个文本的指纹中的每个项目并执行 1 个比较操作（对于 l 长度切片），如果有一些项目，则对于某个常数 'm'哈希表中的相同索引。

于 2013-06-01T15:30:00.913 回答