algorithm - 如果 L 和 M 是 Linked List ，在什么条件下是 LM = ML

Question

这是 Ullman 的 List Data Model 中的一个问题

• 如果 L 和 M 是 Linked List ，在什么条件下是 LM = ML ？

我正在阅读计算机科学基础书籍。问题来自http://i.stanford.edu/~ullman/focs/ch06.pdf 6.3.2

Answer 1

我能想到两个条件：

其中一个列表是空的。

{}+{1,2,3} = {1,2,3}+{} = {1,2,3}

一个列表是另一个列表的多个实例的串联。

{1,2,3}+{1,2,3,1,2,3} = {1,2,3,1,2,3}+{1,2,3} = {1,2,3,1,2,3,1,2,3}

两个旁注：1）在第一个条件中，空列表{}是连接操作的标识。2）条件M=L实际上是条件二的特例。

编辑：感谢@jwpat7，这是另一个条件：

{2,3,2,3}+{2,3,2,3,2,3} = {2,3,2,3,2,3}+{2,3,2,3}

两个列表都是同一列表的多个实例的串联，{2,3}如上例所示。

Answer 2

不失一般性，我们可以假设 |L| <= |M|。（否则只需颠倒标签 L 和 M 的分配。）然后我们有 LM = ML = LAL，其中 M = LA = AL。请注意，我们现在有一个相同问题的新版本，用 LA 替换 LM。这说明我们可以给出一个递归条件：

LM = ML if and only if M = AL = LA for some list A 

Answer 3

有一个鲜为人知的定理（最近在这里使用：Detect if sequence is a multiple of a subsequence in Python）

根据该定理，假设 x 和 y 是字符串。则 xy = yx if an 仅当x 和 y 都是某个字符串 z 的幂，即两者都是同一字符串 z 的串联，即 x= zzz..z (k 次) 和 y = zz..z (l次）。

用“普通的旧”链表来谈论本质上是相同的。

我相信通过归纳证明其中一个字符串的长度是有效的。

（不幸的是，我曾经记得这个定理的名称，但我忘记了，所以找不到你的参考）。