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
>>MUI
MI[III]
>>MIU
MUIIIUIIIU
podría cederMU[III]UIIIU
>>MUUUIIIU
MUIIIU[III]U
>>MUIIIUUU
MUIIIIU
podría cederMU[III]IU
>>MUUIU
MUI[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).