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
 

CgpkZWYgbWF0Y2hMaW5lYXIocGF0dGVybiwgbmFtZSk6CiAgICBweCA9IDAKICAgIG54ID0gMAogICAgbmV4dFB4ID0gMAogICAgbmV4dE54ID0gMAogICAgaXRlcmF0aW9ucyA9IDAKICAgIHRyeToKICAgICAgICB3aGlsZSBweCA8IGxlbihwYXR0ZXJuKSBvciBueCA8IGxlbihuYW1lKToKICAgICAgICAgICAgaXRlcmF0aW9ucyArPSAxCiAgICAgICAgICAgIGlmIHB4IDwgbGVuKHBhdHRlcm4pOgogICAgICAgICAgICAgICAgYyA9IHBhdHRlcm5bcHhdCiAgICAgICAgICAgICAgICBpZiBjID09ICc/JzoKICAgICAgICAgICAgICAgICAgICBpZiBueCA8IGxlbihuYW1lKToKICAgICAgICAgICAgICAgICAgICAgICAgcHggKz0gMQogICAgICAgICAgICAgICAgICAgICAgICBueCArPSAxCiAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgICAgICBlbGlmIGMgPT0gJyonOgogICAgICAgICAgICAgICAgICAgIG5leHRQeCA9IHB4CiAgICAgICAgICAgICAgICAgICAgbmV4dE54ID0gbnggKyAxCiAgICAgICAgICAgICAgICAgICAgcHggKz0gMQogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIGlmIG54IDwgbGVuKG5hbWUpIGFuZCBuYW1lW254XSA9PSBjOgogICAgICAgICAgICAgICAgICAgICAgICBweCArPSAxCiAgICAgICAgICAgICAgICAgICAgICAgIG54ICs9IDEKICAgICAgICAgICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgaWYgMCA8IG5leHROeCBhbmQgbmV4dE54IDw9IGxlbihuYW1lKToKICAgICAgICAgICAgICAgIHB4ID0gbmV4dFB4CiAgICAgICAgICAgICAgICBueCA9IG5leHROeAogICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgcmV0dXJuIEZhbHNlCiAgICAgICAgcmV0dXJuIFRydWUKICAgIGZpbmFsbHk6CiAgICAgICAgcmV0dXJuIGl0ZXJhdGlvbnMKCgpmb3IgcGF0dGVybl9sZW4gaW4gWzEwLCA1MCwgMTAwXToKICAgIHByaW50ICJQYXR0ZXJuIGxlbiIsIHBhdHRlcm5fbGVuCiAgICBmb3IgaSBpbiB4cmFuZ2UoMSwgMTUpOgogICAgICAgIHBhdHRlcm4gPSAnYSonICsgJ2EnICogKHBhdHRlcm5fbGVuIC0gMykgKyAnYicKICAgICAgICBuYW1lX2xlbiA9IDIgKiogaQogICAgICAgIG5hbWUgPSAnYScgKiBuYW1lX2xlbgogICAgICAgIGl0ID0gbWF0Y2hMaW5lYXIocGF0dGVybiwgbmFtZSkKICAgICAgICBwcmludCBpdCwgbmFtZV9sZW4gKiBwYXR0ZXJuX2xlbgo=