常量tim中的字符串比较

Question

我在想比较两个字符串的更快的方法。 检查Python集合（哈希表）中是否存在值的时间是常量。 这是否意味着在集合中查找字符串也有固定的时间？你知道吗

print('tya' == 'tya') #O(n)
mySet = set()
mySet.add('tya')
if 'tya' in mySet: #O(1) <-- ???
    print('True')

在更一般的情况下，这是否意味着我可以在线性时间内在字符串中找到子字符串？？？你知道吗

def NaiveFind(largeString, subString):
    mySet = set()
    mySet.add(subString)
    index = -1
    start = 0
    end = len(subString)

    while(end < len(largeString)): #O(n-m)
        windowFromLarge = largeString[start:end]
        if(windowFromLarge in mySet): #O(1) <------- LINEAR ???
        #if(windowFromLarge == subString): #O(m)
            return start
        start += 1
        end += 1

    return index

Answer 1

你说呢

Checking if value exists in Python set (hash table) has constant time.

但这是一种常见的过于简单化的说法，因为人们没有意识到自己在这么做，或者每次说出实际的行为都需要更长的时间。你知道吗

检查Python集中是否存在一个值需要一个平均大小写常量个哈希运算和相等比较，假设哈希冲突不会失控。它不会自动使哈希运算和相等比较的时间保持不变。你知道吗

您的NaiveFind算法不是线性时间，因为您忽略了哈希计算的成本（而且字符串切片需要CPython中的一个副本）。Rabin-Karp algorithm使用了您想法的精练版本，其中散列是rolling hash以避免这个问题。Rabin-Karp算法是平均情况下的线性时间，只要哈希冲突不失控。还有像Knuth-Morris-Pratt这样保证线性时间的算法，像Boyer-Moore这样的算法在通常情况下比线性时间做得更好。你知道吗