Finding patterns in a list

Question

I'm trying to write a python script to find patterns in a list.

Eg. Given this list

[1,2,3,4,5,6,4,5,6,4,5,6,4,5,6]

The script would determine that 4,5,6 ocurred 3 times and then print out

3 (4,5,6)

I was hoping if anyone had any insights algorithmically (I can only think of n^2 algorithms where I check for patterns of size 1, then 2, then 3, etc iterating through the string each time) or if there might be any Python built-in libraries which might help do the same things. Thanks!

Answer 1

Here is a function providing a solution to the pattern matching problem:

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

To solve the stated problem, call with:

p = [4, 5, 6]
l = [1, 2, 3, 4, 5, 6, 4, 5, 6, 4, 5, 6, 4, 5, 6]
count = pattern_match(p, l)

Here is a Gist with the complete code solving the example problem.

(I believe the correct answer is that the pattern repeats 4 times, not 3 times, as stated in the question.)

I'm not sure if the complexity of this algorithm is actually less than O(n^2).