确定一个序列是否包含在另一个序列中的最佳方法是什么？

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

到目前为止，我只依赖于暴力方法，但它似乎缓慢、丑陋而笨拙。

- Gregg Lind

---

这个回答解决了你的问题吗？在Python中检查切片列表是否存在 - user202729

Answer 1

我赞同使用Knuth-Morris-Pratt算法。顺便说一下，你的问题（以及KMP解决方案）正是《Python Cookbook》第二版中的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)

- Federico Ramponi

---

请注意，code.activestate上提供的KMP实现在某些情况下（可能是不典型的输入）被证明比原来慢30-500倍。进行基准测试以查看是否普通内置方法优于它似乎是一个好主意！ - James Brady

实际上，KMP算法的速度大约是朴素算法的两倍。因此，尽管其渐进最坏时间复杂度很好，但对于大多数情况来说，它完全不适用。 - Konrad Rudolph

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()

我想知道在这种情况下“小”有多小？

- J.F. Sebastian

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

- vexed

---

我喜欢它！对于快速而简单的东西，这样做还不错。一般来说：def is_in(seq1, seq2): return str(list(seq1))[1:-1] in str(list(seq2))[1:-1]我猜这不是找到匹配索引的好方法。 - sfink

有点牵强，但这并不能区分相邻的元素和组合的元素，所以["'a','b'"]会出现在["a","b"]中，即使术语'a','b'在该列表中不存在。 - KyleMit

Answer 4

这与字符串匹配是一样的，先生...Knuth-Morris-Pratt字符串匹配算法

- nlucaroni

Answer 5

>>> def seq_in_seq(subseq, seq):
...     while subseq[0] in seq:
...         index = seq.index(subseq[0])
...         if subseq == seq[index:index + len(subseq)]:
...             return index
...         else:
...             seq = seq[index + 1:]
...     else:
...         return -1
... 
>>> seq_in_seq([5,6], [4,'a',3,5,6])
3
>>> seq_in_seq([5,7], [4,'a',3,5,6])
-1

抱歉，我不是算法专家，这只是我目前能想到的最快的方法，至少我认为它看起来很好（对我来说），我编写它时很开心。;-)

很可能这就是您的暴力解决方案所做的事情。

- mcella

---

它很简洁，但是有些暴力 --> O(mn) - Gregg Lind

Answer 6

对于小型模式，暴力破解可能是可以的。

但对于更大的模式，请查看Aho-Corasick算法。

- Doug Currie

---

Aho-Corasick很不错。我特别寻找Python或类Python的解决方案...所以如果有一个实现，那就太好了。我会自己探索一下。 - Gregg Lind

Answer 7

这是另一种KMP算法的实现：

from itertools import tee

def seq_in_seq(seq1,seq2):
    '''
    Return the index where seq1 appears in seq2, or -1 if 
    seq1 is not in seq2, using the Knuth-Morris-Pratt algorithm

    based heavily on code by Neale Pickett <[e-mail]>
    found at:  woozle.org/~neale/src/python/kmp.py

    >>> seq_in_seq(range(3),range(5))
    0
    >>> seq_in_seq(range(3)[-1:],range(5))
    2
    >>>seq_in_seq(range(6),range(5))
    -1
    '''
    def compute_prefix_function(p):
        m = len(p)
        pi = [0] * m
        k = 0
        for q in xrange(1, m):
            while k > 0 and p[k] != p[q]:
                k = pi[k - 1]
            if p[k] == p[q]:
                k = k + 1
            pi[q] = k
        return pi

    t,p = list(tee(seq2)[0]), list(tee(seq1)[0])
    m,n = len(p),len(t)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(n):
        while q > 0 and p[q] != t[i]:
            q = pi[q - 1]
        if p[q] == t[i]:
            q = q + 1
        if q == m:
            return i - m + 1
    return -1

- Gregg Lind

---

“tee”调用似乎没有什么用，因为忽略了tee输出2元组中的另一个元素。 “seq1”和“seq2”分别复制到两个新生成器中，其中一个被实例化为列表，另一个被忽略。 - j0057

Answer 8

我来晚了，但这里有一个使用字符串的简单示例：

>>> def seq_in_seq(sub, full):
...     f = ''.join([repr(d) for d in full]).replace("'", "")
...     s = ''.join([repr(d) for d in sub]).replace("'", "")
...     #return f.find(s) #<-- not reliable for finding indices in all cases
...     return s in f
...
>>> seq_in_seq([5,6], [4,'a',3,5,6])
True
>>> seq_in_seq([5,7], [4,'a',3,5,6])
False
>>> seq_in_seq([4,'abc',33], [4,'abc',33,5,6])
True

正如Ilya V. Schurov所指出的那样，在这种情况下，find方法对于多字符字符串或多位数数字将无法返回正确的索引。

- Michael Anderson

---

这个解决方案在序列元素具有非唯一长度的情况下不可靠：很难将返回的索引转换为初始序列中的索引。请注意，对于Python 3，\d``语法的反引号已被弃用并不鼓励使用。 - Ilya V. Schurov

即使所有字符串长度相同，也存在不可靠性的示例：子串='ab'，完整字符串='aa'，'bb'。 - makapuf

Answer 9

就我所知，我尝试使用双端队列，如下：

from collections import deque
from itertools import islice

def seq_in_seq(needle, haystack):
    """Generator of indices where needle is found in haystack."""
    needle = deque(needle)
    haystack = iter(haystack)  # Works with iterators/streams!
    length = len(needle)
    # Deque will automatically call deque.popleft() after deque.append()
    # with the `maxlen` set equal to the needle length.
    window = deque(islice(haystack, length), maxlen=length)
    if needle == window:
        yield 0  # Match at the start of the haystack.
    for index, value in enumerate(haystack, start=1):
        window.append(value)
        if needle == window:
            yield index

deque实现的一个优点是它只对干草堆进行一次线性遍历。因此，如果干草堆是流式的，则它仍将工作（不像依赖于切片的解决方案）。

该解决方案仍然是暴力的，O(n*m)。一些简单的本地基准测试显示它比str.index中的C实现字符串搜索慢了约100倍。

- GrantJ

Answer 10

另一种方法是使用集合：

set([5,6])== set([5,6])&set([4,'a',3,5,6])
True

- miguelghz

---

仅仅判断集合是否是序列的子集，而不考虑它们在序列中的顺序。例如，set([5,6])== set([5,6])&set([4,'a',5,4,6]) 返回 True。 - Jonas Lindeløv

这可能是一个第一次快速测试：检查所有元素是否在完整列表中。 - makapuf

但是这个“快速测试”是否比真正的测试更快并不明显... 至少在渐近意义下，它更慢：如果m和n是小序列和大序列的长度，则构建集合并测试包含关系是O(log(m+n))，而像KMP这样的聪明算法测试子序列包含是O(m+n)。对于小序列，我还怀疑只是朴素的子序列算法（O(m×n)）在实践中比子集测试更快，因为它不构建对象，因此没有开销。 - Maëlan

打字错误：我是说“构建集合并测试其包含性的时间复杂度为O((m+n)×log(m+n))”。 - Maëlan