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.
--
http://mail.python.org/mailman/listinfo/python-list
