Google Code Jam Japan 2011 決勝 C. ワイルドカード (Small)

GCJ

ワイルドカード

答えは、Aのいくつかの部分文字列で*を挟んだ形になっている。全て生成して、Bにマッチしないかどうか調べる。

import re

def solve(A,B):
    n = len(A)
    ans = A
    for i in xrange(1<<n):
        p = "".join(A[i] if i>>j&1 else "*" for j in range(n))
        p = re.sub("\*+","*",p)
        if ( len(p)< len(ans) or
             len(p)==len(ans) and p.count("*")< ans.count("*") or
             len(p)==len(ans) and p.count("*")==ans.count("*") and p<ans ):
            if not re.match("^"+p.replace("*",".*")+"$",B):
                ans = p
    return ans

for t in xrange(input()):
    A = raw_input()
    B = raw_input()
    ans = solve_small(A,B)
    print "Case #%s: %s" % (t+1,ans)