对于 2 个字符串，我想找出不同 LCS 的数量。我在 wiki 上阅读了如何打印所有 LCS，但如何检查它们是否不同？哈希表不可行，因为我的输入字符串每个可以有 1500-2000 个字符长，所以 LCS 的最大数量可以是 2000，选择 1000
最佳答案
找到每个子序列后，将它们插入 trie 的惰性版本中.
Trie 存在内存浪费问题。因此，不是将值存储到最后，而是仅在需要解决冲突时才分支。
例如。安娜，应用程序，安妮
最初，根节点中会有 anna。
当您尝试插入应用程序时，您意识到根目录下已经有一个字符串，因此在 a 中创建一个分支并尝试放入 anna 和应用程序。冲突一直持续到你 split 成anna 和apps。
目前，trie 看起来像:
a
(anna) n p (apps)
现在当您插入 anne 时，您将到达 an 并意识到存在冲突并通过添加 n 分支和 a 来解决它> 和 e 分支机构。
最终的 trie 将如下所示:
a
n p (apps)
n
(anna) a e (anne)
关于algorithm - 找出唯一的最长公共(public)子序列的数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1660641/