algorithm - 如何检测文本替换是否导致无限循环？

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. 执行替换脚本时检测到无限循环（这样我可以中止操作并通知用户）。

我不知道从哪里开始。我已经考虑了两个多星期，但一无所获。

标签： algorithmlanguage-agnostic

Answer 1

如果第一个脚本的 ORIG 是第二个脚本的 BECOMES 的一部分，您可以尝试使用代表替换脚本的节点和连接一个脚本与另一个脚本的边构建一个图。

然后你可以在这个图中搜索循环，告诉你你可以无限期地应用这个循环中的规则。