0

我正在阅读这篇关于计算两个字符串之间不同公共子序列数量的论文，该论文描述了一种 DP 方法来做同样的事情。现在，当有两个以上的字符串必须找到其数量不同的公共子序列时，它可能会采用与此不同的方法。我想要的是，这个任务是否可以在时间复杂度小于指数的情况下实现，以及如何完成？

4

1 回答 1

1

如果您有一个大小为 的字母表和最多大小为大小k的m字符串，n那么（假设所有单独的数学运算都是O(1)）这个问题最多可以通过时间和内存的动态规划来解决。这些并不是严格的界限，实际上性能和内存应该比这要好得多。但在实际使用长字符串时，您最终会需要大整数运算，这将使数学运算不是. 它仍然是多项式的。O(k nm+1)O(k nm)O(1)

这是一个令人遗憾的令人困惑的句子中的技巧。我们想要建立一系列表格，列出每个可能的子序列长度和从每个字符串中选择一个字符副本的每组方法，不同子序列的数量，每个字符串中的最小表达式以所选结尾点。如果我们这样做，那么所有这些值的总和就是我们的最终答案。

这是如何做到这一点的大纲（您可以在不理解上述描述的情况下做到这一点）。

  1. 对于每个字符串，建立一个转换表映射（字符串中的位置，字符）到该字符下一次出现的位置。表格应从第一个字符之前的位置 0 开始。您可以使用 -1 来运行字符串的末尾。

  2. 创建一个数据结构，将与您拥有的字符串数相同大小的整数列表映射到另一个整数。这将是固定长度的子序列的计数，其在每个字符串中的最短表示在该组位置处结束。

  3. 插入作为唯一值(0, 0, ..., 0) -> 1表示存在 1 个长度为 0 的子序列，并且每个字符串中的最短表示在开头结束。

  4. 将公共子序列的总数设置为 0。

  5. 虽然该地图不是空的：

    1. 将该映射中的值的总和添加到公共子序列的总数中。

    2. 创建第二个相同类型的地图，但没有数据。

    3. 对于第一个映射中的每个键/值对：

      1. 对于字母表中每个可能的字符：

        1. 通过获取每个字符串，查看位置，然后获取该字符的下一个位置，构造一个新的整数向量作为新键。当然，如果你跑出字符串的末尾，请跳出循环。

        2. 如果该键不在您的第二张地图中，请将其插入值为 0。

        3. 将第二个映射中该键的值增加当前映射中的当前值。（基本上添加刚刚具有此最小字符转换的子序列的数量。）

    4. 将第二个数据结构复制到第一个。

  6. 所有字符串中共有的不同子​​序列的总数现在应该是正确的。

于 2013-06-27T18:28:02.843 回答