我如何测试一个列表是否包含另一个列表(即它是一个连续的子序列).假设有一个名为 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它返回一个 (start, end+1) 元组,因为我认为这更像 Pythonic,正如 Andrew Jaffe 在他的评论中指出的那样.它不会对任何子列表进行切片,因此应该相当高效.
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.
新手感兴趣的一点是它使用 for 语句中的else 子句 - 这不是我经常使用的东西,但在这种情况下非常有用.
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.
这与在字符串中查找子字符串相同,因此对于大型列表,实现诸如 Boyer-Moore 算法.
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.
注意:如果您使用的是 Python3,请将 xrange 更改为 range.
Note: If you are using Python3, change xrange to range.
更多推荐
如何测试一个列表是否包含另一个列表作为连续子序列?
发布评论