如何测试一个列表是否包含另一个列表作为连续子序列?

本文介绍了如何测试一个列表是否包含另一个列表作为连续子序列?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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