python之最长公共(public)子串，Python复杂度分析

我构建了一个函数，该函数基于 Rabin–Karp 算法按升序查找两个文本文件的最长公共(public)子串。 主要功能是“find_longest”，内部功能是:“make_hashtable”、“extend_fingerprints”和“has_match”。 我在分析 has_match 的平均情况复杂性时遇到问题。

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

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 称为体面哈希函数的最佳选择，因此几乎没有冲突，这意味着如果两个文本在哈希表中是相同的单元格，我们可以假设它们实际上是相同的文本？

我个人倾向于大胆的说法。 谢谢。

请您参考如下方法:

我认为答案是

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

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