检查Python中是否存在切片列表

Question

我想编写一个函数来确定子列表是否存在于更大的列表中。

list1 = [1,0,1,1,1,0,0]
list2 = [1,0,1,0,1,0,1]

#Should return true
sublistExists(list1, [1,1,1])

#Should return false
sublistExists(list2, [1,1,1])

有没有一个Python函数可以做到这一点？

Answer 1

如果您确定输入将只包含个位数0和1，则可以转换为字符串：

def sublistExists(list1, list2):
    return ''.join(map(str, list2)) in ''.join(map(str, list1))

这将创建两个字符串，因此它不是最有效的解决方案，但由于它利用了Python中优化的字符串搜索算法，因此对于大多数目的来说，它可能已经足够好了。

如果效率非常重要，您可以查看Boyer-Moore字符串搜索算法，该算法适合处理列表。

天真的搜索有O（n*m）最坏的情况，但如果您不能使用转换为字符串的技巧，并且不需要担心性能，则可以使用天真的搜索。

Answer 2

让我们来点功能，好吗？：）

def contains_sublist(lst, sublst):
    n = len(sublst)
    return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1))

注意，any()将在lst中的子列表的第一次匹配时停止，或者在O（m*n）操作之后，如果没有匹配，则失败

Answer 3

我不知道有什么功能

def sublistExists(list, sublist):
    for i in range(len(list)-len(sublist)+1):
        if sublist == list[i:i+len(sublist)]:
            return True #return position (i) if you wish
    return False #or -1

正如马克所指出的，这不是最有效的搜索（它是O（n*m））。这个问题可以用与字符串搜索几乎相同的方法来解决。