(a|b|^)(c|d|^)foo
((a|b)?(c|d)|c|d)?foo
((.*a|.*b)(c|d)|c|d)?foo
In an engine supporting ^ and $, searching for this
^((.*a|.*b)(c|d)|c|d)?foo.*$