Welcome, guest | Sign In | My Account | Store | Cart

Search sequences for sub-sequence (Python recipe) by Steven D'Aprano
ActiveState Code (http://code.activestate.com/recipes/577850/)

The list and tuple index() method and in operator test for element containment, unlike similar tests for strings, which checks for sub-strings:

>>> "12" in "0123"
True
>>> [1, 2] in [0, 1, 2, 3]
False

These two functions, search and rsearch, act like str.find() except they operate on any arbitrary sequence such as lists:

>>> search([1, "a", "b", 2, 3], ["b", 2])
2
Python, 42 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def _search(forward, source, target, start=0, end=None):
    """Naive search for target in source."""
    m = len(source)
    n = len(target)
    if end is None:
        end = m
    else:
        end = min(end, m)
    if n == 0 or (end-start) < n:
        # target is empty, or longer than source, so obviously can't be found.
        return None
    if forward:
        x = range(start, end-n+1)
    else:
        x = range(end-n, start-1, -1)
    for i in x:
        if source[i:i+n] == target:
            return i
    return None

import functools
search = functools.partial(_search, True)
rsearch = functools.partial(_search, False)


_doc = """\
%(name)s(sequence, subsequence [, start [, end]]) -> int or None

Search a sequence[start:end] for a subsequence starting from the %(dir)s,
returning the offset if it is found, otherwise None.

>>> %(name)s([1, 2, "z", 2, "a", 3, 2, "a"], [2, "a"])
%(value)d

If not given, start and end default to the beginning and end of the sequence.
"""

search.__doc__ = _doc % {'name': 'search', 'value': 3, 'dir': 'left'}
rsearch.__doc__ = _doc % {'name': 'rsearch', 'value': 6, 'dir': 'right'}
search.__name__ = 'search'
rsearch.__name__ = 'rsearch'
del _doc, _search

search() searches from the left, rsearch() searches backwards from the right, similar to the str methods find and rfind. Both take optional start and end indexes to limit the search.

Unlike str.find(), these return None if the sub-sequence is not found, instead of -1. This avoids the common error with str.find that -1 is a valid index into the string.

The search algorithm is not especially efficient, it is a simple, naive search, but for small lists it should be plenty fast enough.

Tags: find, searching, sequence, string, sublist, substring