So, have the regex engine do what it does best, that is, return the longest matching string. Then, have a routine that takes that string and provides the permutations.