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

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

Answer 1

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

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