Лучший способ определить, входит ли последовательность в другую?

Я поддерживаю алгоритм Кнута-Морриса-Пратта. Кстати, ваша проблема (и решение KMP) - это в точности рецепт 5.13 в Поваренная книга Python, 2-е издание. Вы можете найти соответствующий код на странице 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)

Вот подход грубой силы O(n*m) (аналогичный ответ @ mcella). Это может быть быстрее, чем реализация алгоритма Кнута-Морриса-Пратта на чистом Python O(n+m) (см. @ Gregg Lind answer) для небольших входных последовательностей.

#!/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()

Интересно, насколько велик маленький в этом случае?

Простой подход: преобразовать в строки и полагаться на сопоставление строк.

Пример использования списков строк:

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

То же, что и сопоставление строк, сэр ... сопоставление строк Кнута-Морриса-Пратта

Для более крупных обращайтесь к алгоритму Ахо-Корасика.

Вот еще одна реализация 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 <[email protected]>
    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

Я немного опоздал на вечеринку, но вот что-то простое с использованием строк:

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

Как заметил Илья В. Щуров, метод find в этом случае не вернет правильные индексы с многосимвольными строками или многозначными числами.

Другой подход, использующий наборы:

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

Как бы то ни было, я пробовал использовать такую ​​двухстороннюю очередь:

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

Одним из преимуществ реализации двухсторонней очереди является то, что она выполняет только один линейный проход по стогу сена. Поэтому, если стог сена транслируется, он все равно будет работать (в отличие от решений, основанных на нарезке).

Решение по-прежнему - грубая сила, O (n * m). Некоторые простые локальные тесты показали, что он был примерно в 100 раз медленнее, чем C-реализация поиска по строкам в str.index.