ordermatch

x = "001111111010001"
t = "0101"

def match(i, j, prev=[]):
    if i == len(x) or j == len(t):
        if len(prev) == 4:
            print prev, "".join(x[k] for k in prev)
            return 1
        return 0
    if x[i] == t[j]:
        c1 = match(i + 1, j + 1, prev + [i])
    else:
        c1 = 0
    c2 = match(i + 1, j, prev)
    return c1 + c2
    
print match(0, 0, [])

"""
[0, 2, 9, 10] 0101
[0, 2, 9, 14] 0101
[0, 2, 11, 14] 0101
[0, 2, 12, 14] 0101
[0, 2, 13, 14] 0101
[0, 3, 9, 10] 0101
[0, 3, 9, 14] 0101
[0, 3, 11, 14] 0101
[0, 3, 12, 14] 0101
[0, 3, 13, 14] 0101
[0, 4, 9, 10] 0101
[0, 4, 9, 14] 0101
[0, 4, 11, 14] 0101
[0, 4, 12, 14] 0101
[0, 4, 13, 14] 0101
[0, 5, 9, 10] 0101
[0, 5, 9, 14] 0101
[0, 5, 11, 14] 0101
[0, 5, 12, 14] 0101
[0, 5, 13, 14] 0101
[0, 6, 9, 10] 0101
[0, 6, 9, 14] 0101
[0, 6, 11, 14] 0101
[0, 6, 12, 14] 0101
[0, 6, 13, 14] 0101
[0, 7, 9, 10] 0101
[0, 7, 9, 14] 0101
[0, 7, 11, 14] 0101
[0, 7, 12, 14] 0101
[0, 7, 13, 14] 0101
[0, 8, 9, 10] 0101
[0, 8, 9, 14] 0101
[0, 8, 11, 14] 0101
[0, 8, 12, 14] 0101
[0, 8, 13, 14] 0101
[0, 10, 11, 14] 0101
[0, 10, 12, 14] 0101
[0, 10, 13, 14] 0101
[1, 2, 9, 10] 0101
[1, 2, 9, 14] 0101
[1, 2, 11, 14] 0101
[1, 2, 12, 14] 0101
[1, 2, 13, 14] 0101
[1, 3, 9, 10] 0101
[1, 3, 9, 14] 0101
[1, 3, 11, 14] 0101
[1, 3, 12, 14] 0101
[1, 3, 13, 14] 0101
[1, 4, 9, 10] 0101
[1, 4, 9, 14] 0101
[1, 4, 11, 14] 0101
[1, 4, 12, 14] 0101
[1, 4, 13, 14] 0101
[1, 5, 9, 10] 0101
[1, 5, 9, 14] 0101
[1, 5, 11, 14] 0101
[1, 5, 12, 14] 0101
[1, 5, 13, 14] 0101
[1, 6, 9, 10] 0101
[1, 6, 9, 14] 0101
[1, 6, 11, 14] 0101
[1, 6, 12, 14] 0101
[1, 6, 13, 14] 0101
[1, 7, 9, 10] 0101
[1, 7, 9, 14] 0101
[1, 7, 11, 14] 0101
[1, 7, 12, 14] 0101
[1, 7, 13, 14] 0101
[1, 8, 9, 10] 0101
[1, 8, 9, 14] 0101
[1, 8, 11, 14] 0101
[1, 8, 12, 14] 0101
[1, 8, 13, 14] 0101
[1, 10, 11, 14] 0101
[1, 10, 12, 14] 0101
[1, 10, 13, 14] 0101
[9, 10, 11, 14] 0101
[9, 10, 12, 14] 0101
[9, 10, 13, 14] 0101
79
"""

# here is the code use lur_cache

from functools import lru_cache

def match(x, t):
    @lru_cache(None)
    def match_count(i, j):
        if i == len(x) or j == len(t):
            if j == len(t):
                return 1
            return 0
        c1 = match_count(i + 1, j + 1) if x[i] == t[j] else 0
        c2 = match_count(i + 1, j)
        return c1 + c2

    return match_count(0, 0)

print(match("001111111010001", "0101"))