testing if a list contains a sublist

Nobody nobody at nowhere.com
Wed Aug 17 14:28:42 CEST 2011


On Tue, 16 Aug 2011 09:57:57 -0400, John Posner wrote:

> How about using Python's core support for "==" on list objects:

>     for i in range(alist_sz - slist_sz + 1):
>         if slist == alist[i:i+slist_sz]:
>             return True

This is bound to be asymptotically O(alist_sz * slist_sz), even if the
constant factor is reduced by use of ==. Boyer-Moore and regexps are
asymptotically O(alist_sz). However, the setup costs are much higher, so
you might need alist_sz to be very large before they win out.




More information about the Python-list mailing list