あるリストが他のリストを連続した部分配列として含んでいるかどうかを調べるには？

質問

あるリストが他のリストを含んでいるかどうか（つまり連続した部分列であるかどうか）を調べるにはどうしたらよいでしょうか。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) のタプルを返します。Andrew Jaffeがコメントで指摘しているように、この方がよりpythonicだと思うからです。 これはサブリストをスライスしないので、合理的に効率的であるべきです。

初心者のための1つの興味ある点は、このメソッドが for文のelse節 - これは私が頻繁に使うものではありませんが、このような状況では非常に貴重です。

これは文字列の部分文字列を見つけるのと同じです。ですから、大きなリストでは Boyer-Mooreアルゴリズム .

注意してください。 Python3を使っている場合は xrange を range .