# A pattern matching problem

Developing software involves solving an indefinite number of small pattern matching problems. Recently I had to find a simple way to match a specific pattern of heartbeats in a parsed ECG signal.

The problem can be reduced to this: Return the number of occurrences of a pattern, say `[4,5,6]`, in a longer sequence, such as `[1,2,3,4,5,6,4,5,6,4,5,6,4,5,6]`.

I’m sure this problem has been solved a millions times over in computing history. But, besides regular expressions (which deals with text strings), I didn’t find a straightforward solution in Python’s standard library.

Looking for a solution, I came across Stack Overflow (SO) where someone else, having the same problem, posted it as a question. The accepted answer outlined an algorithm, but didn’t provide any code.

Therefore, I came up with my own solution, which I posted on SO, and repeat here (Python code):

``````import itertools

def pattern_match(pattern, sequence):
"""Count the number of times that pattern
occurs in the sequence.
"""
pattern = tuple(pattern)
k = len(pattern)

# create k iterators for the sequence
i = itertools.tee(sequence, k)

# advance the iterators
for j in range(k):
for _ in range(j):
next(i[j])

count = 0
for q in zip(*i):
if pattern == q:
count += 1

return count
``````

Here is a Gist solving the example problem above, which was posed in the SO question.

If you are curious, the answer is 4.