如何测试一个列表是否包含另一个列表? [英] How to test if a list contains another list?

问题描述

如何测试一个列表是否包含另一个列表(即它是连续的子序列).假设有一个名为contains的函数

How can I test if a list contains another list (ie. it's a contiguous subsequence). Say there was a function called contains:

contains([1,2], [-1, 0, 1, 2]) # Returns [2, 3] (contains returns [start, end])
contains([1,3], [-1, 0, 1, 2]) # Returns False
contains([1, 2], [[1, 2], 3]) # Returns False
contains([[1, 2]], [[1, 2], 3]) # Returns [0, 0]

contains([2, 1], [-1, 0, 1, 2]) # Returns False
contains([-1, 1, 2], [-1, 0, 1, 2]) # Returns False
contains([0, 1, 2], [-1, 0, 1, 2]) # Returns [1, 3]

推荐答案

这是我的版本:

def contains(small, big):
    for i in xrange(len(big)-len(small)+1):
        for j in xrange(len(small)):
            if big[i+j] != small[j]:
                break
        else:
            return i, i+len(small)
    return False

正如安德鲁·贾菲(Andrew Jaffe)在其评论中指出的那样，它返回一个元组(start，end + 1)，因为我认为这更Python化.它不对任何子列表进行切片，因此应该相当有效.

It returns a tuple of (start, end+1) since I think that is more pythonic, as Andrew Jaffe points out in his comment. It does not slice any sublists so should be reasonably efficient.

新手感兴趣的一点是，它使用

One point of interest for newbies is that it uses the else clause on the for statement - this is not something I use very often but can be invaluable in situations like this.

这与在字符串中查找子字符串相同，因此对于大型列表，实施

This is identical to finding substrings in a string, so for large lists it may be more efficient to implement something like the Boyer-Moore algorithm.

这篇关于如何测试一个列表是否包含另一个列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！