如何测试一个列表是否包含另一个列表作为连续子序列? [英] How to test if a list contains another list as a contiguous subsequence?

问题描述

我如何测试一个列表是否包含另一个列表(即它是一个连续的子序列).假设有一个名为 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.

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