[wizofaus]

Isn't that just

    ((a|b)?(c|d)|c|d)?foo

Unless you mean it as a search expression, in which case it's more like

    ((.*a|.*b)(c|d)|c|d)?foo

Which I have to admit was a lot harder to figure out than I thought it would be (and may not even be right!)

[zeroimpl]

Yeah the latter.

In an engine supporting ^ and $, searching for this

    (a|b|^)(c|d|^)foo

is equivalent to searching for this

    ^((.*a|.*b)(c|d)|c|d)?foo.*$

And in this context you can drop the leading/trailing ^/$ since they are implicit.