Python-сообщество

def is_sublist(L, S):
    index = -1
    S_len = len(S)
    stop = len(L)-S_len + 1
    while S_len:
        try:
            index = L.index( S[0], index+1, stop )
            if all( i==L[ind] for ind, i in enumerate(S, index) ):
                return True
        except ValueError: return

def is_sublist(L, S):
    try:
        index = -1
        while 1:
            index = L.index( S[0], index+1 )
            if all( i==L[ind] for ind, i in enumerate(S, index) ):
                return True
    except (ValueError, IndexError): pass

S = list(range(5000))
L = [0]*100000 + S

def is_subsequence(sub_seq, seq):
    """ Return True if sub_seq is subsequnce of seq.
    Used algorithm for solving of the small sample size problem.

    >>> is_subsequence([1, 2], [1, 2, 3])
    True
    >>> is_subsequence([2, 1], [1, 2, 3])
    False
    >>> is_subsequence([1, 2], [1, 22, 3])
    False
    >>> is_subsequence([1, 2, 3], [1, 2])
    False
    >>> is_subsequence([1, 2], [1, 3, 2])
    True
    """
    sub_seq_index = len(sub_seq) - 1
    seq_index = len(seq) - 1
    if sub_seq_index > seq_index:
        return False

    while sub_seq_index and seq_index:
        if sub_seq[sub_seq_index] == seq[seq_index]:
            sub_seq_index -= 1
            seq_index -= 1
        else:
            seq_index -=1
    if (seq_index == 0 and sub_seq_index == 0) or (seq_index and sub_seq_index == 0):
        return True
    else:
        return False

def is_sublist(pattern, seq):
    """ Return True if sub_seq is subsequnce of seq.
    Used Knuth-Morris-Pratt algorithm.

    >>> is_sublist([1, 2], [1, 2, 3])
    True
    >>> is_sublist([2, 1], [1, 2, 3])
    False
    >>> is_sublist([1, 2], [1, 22, 3])
    False
    >>> is_sublist([1, 2, 3], [1, 2])
    False
    >>> is_sublist([1, 2], [1, 3, 2])
    False
    """
    def get_prefix():
        """ Get prefix function
        >>> get_prefix(list('ababaa'))
        [-1, 0, 0, 1, 2, 3, 1]
        """
        prefix = [0]*pattern_length
        j = 0
        for i in range(1, pattern_length):
            while (j>0) and pattern[i]!=pattern[j]:
                j = prefix[j-1]
            if pattern[j] == pattern[i]:
                j += 1
            prefix[i] = j
        return [-1]+prefix

    pattern_length = len(pattern)
    seq_length = len(seq)

    if pattern_length > seq_length:
        return False

    prefix = get_prefix()

    j = 0
    for item in seq:
        while j>=0 and pattern[j]!=item:
            j = prefix[j]

        j += 1
        if j==pattern_length:
            return True

    return False