# Python3: find sub-list

Pythonic way of expressing the simple problem:

Tell if the list `needle` is sublist of `haystack`

``````#!/usr/bin/env python3

def sublist (haystack, needle):

def start ():
i = iter(needle)
return next(i), i

try:
n0, i = start()
for h in haystack:
if h == n0:
n0 = next(i)
else:
n0, i = start()
except StopIteration:
return True
return False
``````
-
So, what's the question? –  Jeff Vanzella Dec 15 '12 at 3:27
@JeffVanzella: Fair point. That's "code review". The question is: "what do you think in general?". –  Dacav Dec 15 '12 at 12:30

### 1. Bug

Here's a case where your function fails:

``````>>> sublist([1,1,2], [1,2])
False
``````

this is because in the `else:` case you go back to the beginning of the needle, but you keep going forward in the haystack, possibly skipping over a match. In the test case, your function tries matching with the alignment shown below, which fails at the position marked `X`:

``````             X
haystack   1,1,2
needle     1,2
``````

Then it starts over from the beginning of the needle, but keeps going forward in the haystack, thus missing the match:

``````               X
haystack   1,1,2
needle         1,2
``````

So after a mismatch you need to go backward an appropriate distance in the haystack before starting over again from the beginning of the needle.

### 2. A better algorithm

It turns out to be better to start matching from the end of the needle. If this fails to match, we can skip forward several steps: possibly the whole length of the needle. For example, in this situation:

``````                  X
haystack  1,2,3,4,6,1,2,3,4,5
needle    1,2,3,4,5
``````

we can skip forward by the whole length of the needle (because `6` does not appear in the needle). The next alignment we need to try is this:

``````                    O O O O O
haystack  1,2,3,4,6,1,2,3,4,5
needle              1,2,3,4,5
``````

However, we can't always skip forward the whole length of the needle. The distance we can skip depends on the item that fails to match. In this situation:

``````                  X
haystack  1,2,3,4,1,2,3,4,5
needle    1,2,3,4,5
``````

we should skip forward by 4, to bring the `1`s into alignment.

Making these ideas precise leads to the Boyer–Moore–Horspool algorithm:

``````def find(haystack, needle):
"""
Return the index at which the sequence `needle` appears in the
sequence `haystack`, or -1 if it is not found, using the Boyer-Moore-
Horspool algorithm. The elements of `needle` and `haystack` must be
hashable.
"""
hn = len(haystack)
nn = len(needle)
skip = {needle[i]: nn - i - 1 for i in xrange(nn - 1)}
i = nn - 1
while i < hn:
for j in xrange(nn):
if haystack[i - j] != needle[-j - 1]:
i += skip.get(haystack[i], nn)
break
else:
return i - nn + 1
return -1
``````
-
@Lattyware: Generally I'd agree that you should use iterators wherever it makes sense, but this is one of the exceptional cases where iterators don't make much sense. A pure-iterator search runs in O(nm) whereas Boyer–Moore-Horspool is O(n). (In the average case on random text.) Sometimes you just have to get your hands grubby. –  Gareth Rees Dec 15 '12 at 2:11
Scratch all my arguments, it's impossible to do this correctly the way I was doing it. –  Lattyware Dec 15 '12 at 2:29
Accepted. The source is strong with this one. –  Dacav Dec 15 '12 at 12:38