Programming challenge: wildcard exclusion in cartesian products

[Dinko Tenev]

OK, here's a case that will make your program run in exponential time:
S = { a, b }, W = { *a*b, *b*a } -- on my machine, it starts getting
ugly as soon as n is 15 or so.  Note that S^n - W = { a^n, b^n }.

In general, whenever all the patterns in the set match against the last
position, your current implementation is guaranteed to have to sift
through all of S^n.  I'd say the very idea of checking against a
blacklist is fundamentally flawed, as far as performance is concerned.