Determine if a Sequence is in another sequence in Python : solution 1

/ Published in: Python
Save to your folder(s)

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

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 larger ones, look at the Aho-Corasick algorithm.


Report this snippet


RSS Icon Subscribe to comments

You need to login to post a comment.