代码之家 › 专栏 › 技术社区 › Chao Xu

检查字符串替换规则是否会生成另一个字符串

algorithm

Chao Xu · 技术社区 · 14 年前

不要做作业。

给定两个长度相同的字符串s和t。给定一组替换规则,在S中找到子字符串A,并将其替换为字符串B。 A和B的长度相同。

是否有规则应用程序的序列,使字符串s成为字符串t?

例子: 我们有替换规则

cat->dog
dog->cut

我们有绳子 S1:Awesomecat和S2:Awesomecut

替换顺序可以是

awesomecat 
awesomedog cat->dog
awesomecut dog->cut

这是一个简单的例子,可能有这样的规则。

cat->dog
ate->dog
dog->cat

我相信没有比在每一个状态下尝试每一个规则更好的方法来回答这个问题。这就是指数时间。但我不知道是否有更好的解决办法。

2 回复 | 直到 14 年前

Justin L. 14 年前

我建议你阅读 Godel, Escher, Bach =)它详细讨论了您在这里描述的内容。

总之,一个解决方案是找到 invariant 对于您的系统:如果在操作开始时为真, 在任何情况下都必须 在你的操作结束时也要真实。

如果第一个字符串具有该不变量,而结束字符串没有,则替换规则将从未生成第二个字符串。

您的不变规则可能更强大…例如,它可以是 当且仅当 关系(如果且仅当第一步为真时,在最后一步中的不变量为真),因此,如果第一个字符串中存在不为真的不变量,则可以证明无法访问结束字符串。请注意,如果并且仅当关系自动遵循标准if关系时,如果您的所有规则都是双向工作的(您可以前后应用它们)

例如,在第一个系统中有一个可能的不变量:

考虑到这个不变的规则,很容易提供一个决策公式来决定给定起始字符串的字符串是否可行。

追加

我希望你不介意我采用霍夫施塔特的说法:

所以,你的问题从“x能产生y吗?”到“y是一个有效的定理吗,从x导出?”

那么,让我们从更一般的术语来处理字符串替换问题。我们会打电话 A 所有被替换字符串的有序集,以及 一 所有替换字符串的有序集。因此,这里我们有一个广义规则:

"xA[n]y" => "xB[n]y"

它说,“如果我们看到一个集合中有一个字符串的定理 一 ,由字符串包围 x 和 y 那么我们也可以得出: xB[n]y 在哪里 B[n] 是相应的替换字符串。

让我们找到一些不变量,这是真的, 不管什么是成套的 一 和 B .

例如,如果我们有公理 abcdea 和规则集 A=["cd",de"] 很容易看出字母A和B不在 一 . 因此,我们可以说,这个系统中的所有定理都必须是 ab##a . 这就给了我们一条规则来找出不一个定理。

但是,对于很长的一组 一 这也许对我们没什么帮助,因为 一 可能会用到所有的字母。

让我们试着让这个更有用…

假设我们有 A=["dog","cat","ton"] ,如果一个公理以任何字母结尾, 不是G、T或C , 所有可导定理必须 也以同一个字母结尾。如果一个公理以任何字母开头 不是D、C或T ,所有可导定理必须也可以从同一个字母开始。

这更有用,因为对于任何 一 大小为<26时,您将看到不以字母结尾或开头的字母。然而,对于您的公理来说,以这些特定字母开头或结尾的可能性要小得多。

但是,我们发现我们可以进一步扩展这一点:

我们会发现这更有用! 一 必须至少有26^n个元素大才能将此不变量视为无用。

现在,注意,我们也可以后退!也就是说,我们可以说:

有了这些规则,我组装了一个 decision tree 为了找出我们锁定了哪些案例,哪些案例是无法确定的。你会注意到我们只有两个这样无法确定的案例。

现在剩下的就是找到这两个例子的不变量。但是,我们可以注意到一件事:

也就是说,如果你有 A=["cat","dog"],B=["dog","cut"] 和公理定理 boabcdut boablmut ,然后您可以应用到的任何不变规则 案例2 也可以应用于 cdut => mlut ,使用不匹配的前导字符串 boab 忽略。这大大简化了事情。

所以,我们基本上解决了两个未定案例到一个案例;让我们看看我们还能分析什么……

…又一次。我一会儿再谈。

Yuval Adam 14 年前

您可以很容易地将这个问题映射到一个有向图,其中所有规则都是从一个节点到另一个节点的有向路径。

接收输入时一和乙 ,检查它们之间的差异,并查看是否有一条沿着图生成预期结果的路径。