Как определить, приводит ли замена текста к бесконечному циклу?

Question

Я разрабатываю программу, которая извлекает текст из других программ.Одна из особенностей заключается в том, что пользователи могут указывать «сценарии замены» для обработки текста.Пример сценария замены:

|ORIG|a|BECOMES|bb|END|
|ORIG|b|BECOMES|cc|END|

Процесс замены ищет любой текст ORIG и заменяет его соответствующим текстом BECOMES.Таким образом, если текст aaaa был извлечен, он был бы заменен сначала на bbbbbbbb, а затем на cccccccccccccccc.

Проблема возникает, когда существует сценарий замены, подобный этому:

|ORIG|a|BECOMES|bb|END|
|ORIG|b|BECOMES|aa|END|

и в извлеченном тексте есть a.Это a становится bb, которое становится aaaa, которое становится bbbbbbbb и т. Д. Для бесконечности.

Таким образом, мне нужно два алгоритма: 1. Прочитать сценарий замены и определить, может ли он создатьбесконечный цикл (поэтому я могу предупредить пользователя).2. Обнаружить бесконечный цикл при выполнении сценария замены (чтобы я мог прервать операцию и уведомить пользователя).

Понятия не имею, с чего начать.Я думал об этом более двух недель и ничего не получил.

Answer 1

Если какой-либо ORIG равен или является подстрокой какого-либо BECOMES, то у вас могут возникнуть проблемы.

Answer 2

Вы можете попытаться построить граф с узлами, представляющими заменяющие сценарии, и ребрами, соединяющими один сценарий с другим, если ORIG первого сценария является частью СКОЛЕ второго сценария.

Тогда вы можетепоищите циклы в этом графике, сообщая, что вы можете неограниченно применять правила в этом цикле.