def matchLinear(pattern, name):
    px = 0
    nx = 0
    nextPx = 0
    nextNx = 0
    iterations = 0
    try:
        while px < len(pattern) or nx < len(name):
            iterations += 1
            if px < len(pattern):
                c = pattern[px]
                if c == '?':
                    if nx < len(name):
                        px += 1
                        nx += 1
                        continue
                elif c == '*':
                    nextPx = px
                    nextNx = nx + 1
                    px += 1
                    continue
                else:
                    if nx < len(name) and name[nx] == c:
                        px += 1
                        nx += 1
                        continue
            if 0 < nextNx and nextNx <= len(name):
                px = nextPx
                nx = nextNx
                continue
            return False
        return True
    finally:
        return iterations


for pattern_len in [10, 50, 100]:
    print "Pattern len", pattern_len
    for i in xrange(1, 15):
        pattern = 'a*' + 'a' * (pattern_len - 3) + 'b'
        name_len = 2 ** i
        name = 'a' * name_len
        it = matchLinear(pattern, name)
        print it, name_len * pattern_len