Cómo obtener todas las posibles coincidencias superpuestas para una cadena

Estoy trabajando en el problema del sistema MIU del capítulo 2 de "Gödel, Escher, Bach".

Una de las reglas establece

Rule III: If III occurs in one of the strings in your collection, you may make a new string with U in place of III.

Lo que significa que la cadenaMIII puede llegar a serMU, pero para otras cadenas más largas puede haber múltiples posibilidades [coincidencias entre paréntesis]:

MIIII podría cederM[III]I >>MUIMI[III] >>MIUMUIIIUIIIU podría cederMU[III]UIIIU >>MUUUIIIUMUIIIU[III]U >>MUIIIUUUMUIIIIU podría cederMU[III]IU >>MUUIUMUI[III]U >>MUIUU

Expresiones claramente regulares como/(.*)III(.*)/ son útiles, pero parece que no puedo lograr que generen todas las coincidencias posibles, solo la primera que encuentra.

¿Hay una manera de generar cada partido posible?

(Tenga en cuenta que puedo pensar en maneras de hacer esto de forma completamente manual, pero espero que haya una mejor manera de usar las herramientas integradas, expresiones regulares o de otro tipo)

(Editado para aclarar las necesidades superpuestas).

Respuestas a la pregunta(2)

Su respuesta a la pregunta