确定序列是否在Python中的另一个序列中的最佳方法

Question

这是"字符串包含子字符串"问题到(更多)任意类型的概括.

给定一个序列(例如列表或元组),确定另一个序列是否在其中的最佳方法是什么？作为奖励,它应该返回子序列开始的元素的索引:

用法示例(序列中的序列):

>>> seq_in_seq([5,6],  [4,'a',3,5,6])
3
>>> seq_in_seq([5,7],  [4,'a',3,5,6])
-1 # or None, or whatever

到目前为止,我只是依靠蛮力,它似乎缓慢,丑陋,笨拙.

Answer 1

我是第二个Knuth-Morris-Pratt算法.顺便说一下,你的问题(和KMP解决方案)正是Python Cookbook第2版​​中的配方5.13 .您可以在http://code.activestate.com/recipes/117214/找到相关代码.

它在给定的序列中找到所有正确的子序列,并且应该用作迭代器:

>>> for s in KnuthMorrisPratt([4,'a',3,5,6], [5,6]): print s
3
>>> for s in KnuthMorrisPratt([4,'a',3,5,6], [5,7]): print s
(nothing)

Answer 2

这是一种蛮力的方法O(n*m)(类似于@ mcella的答案).对于小输入序列,它可能比纯Python中的Knuth-Morris-Pratt算法实现更快O(n+m)(参见@Gregg Lind答案).

#!/usr/bin/env python
def index(subseq, seq):
    """Return an index of `subseq`uence in the `seq`uence.

    Or `-1` if `subseq` is not a subsequence of the `seq`.

    The time complexity of the algorithm is O(n*m), where

        n, m = len(seq), len(subseq)

    >>> index([1,2], range(5))
    1
    >>> index(range(1, 6), range(5))
    -1
    >>> index(range(5), range(5))
    0
    >>> index([1,2], [0, 1, 0, 1, 2])
    3
    """
    i, n, m = -1, len(seq), len(subseq)
    try:
        while True:
            i = seq.index(subseq[0], i + 1, n - m + 1)
            if subseq == seq[i:i + m]:
               return i
    except ValueError:
        return -1

if __name__ == '__main__':
    import doctest; doctest.testmod()

我想知道这种情况下的小有多大？

Answer 3

一个简单的方法：转换为字符串并依赖字符串匹配。

使用字符串列表的示例：

 >>> f = ["foo", "bar", "baz"]
 >>> g = ["foo", "bar"]
 >>> ff = str(f).strip("[]")
 >>> gg = str(g).strip("[]")
 >>> gg in ff
 True

使用字符串元组的示例：

>>> x = ("foo", "bar", "baz")
>>> y = ("bar", "baz")
>>> xx = str(x).strip("()")
>>> yy = str(y).strip("()")
>>> yy in xx
True

使用数字列表的示例：

>>> f = [1 , 2, 3, 4, 5, 6, 7]
>>> g = [4, 5, 6]
>>> ff = str(f).strip("[]")
>>> gg = str(g).strip("[]")
>>> gg in ff
True

Answer 4

与字符串匹配先生相同... Knuth-Morris-Pratt字符串匹配