Gregg Lind Gregg Lind - 1 year ago 85
Python Question

Best Way To Determine if a Sequence is in another sequence in Python

This is a generalization of the "string contains substring" problem to (more) arbitrary types.

Given an sequence (such as a list or tuple), what's the best way of determining whether another sequence is inside it? As a bonus, it should return the index of the element where the subsequence starts:

Example usage (Sequence in Sequence):

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

So far, I just rely on brute force and it seems slow, ugly, and clumsy.

Answer Source

I second the Knuth-Morris-Pratt algorithm. By the way, your problem (and the KMP solution) is exactly recipe 5.13 in Python Cookbook 2nd edition. You can find the related code at

It finds all the correct subsequences in a given sequence, and should be used as an iterator:

>>> for s in KnuthMorrisPratt([4,'a',3,5,6], [5,6]): print s
>>> for s in KnuthMorrisPratt([4,'a',3,5,6], [5,7]): print s
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download