12

我正在尝试解决 Cormem 的算法介绍第 3 版（第 405 页）中的动态编程问题，该问题提出以下问题：

回文是一些字母表上的非空字符串，向前和向后读取相同。回文的例子都是长度为 1 的字符串，, civic, racecar, and aibohphobia (fear of palindromes)。

给出一个有效的算法来找到作为给定输入字符串的子序列的最长回文。例如，给定输入 character，您的算法应该返回carac。

好吧，我可以通过两种方式解决它：

第一个解决方案：

字符串的最长回文子序列 (LPS) 只是其自身的最长公共子序列及其反向。（我在解决了另一个要求序列的最长递增子序列的相关问题后构建了这个解决方案）。由于它只是一个 LCS 变体，它还需要 O(n²) 时间和 O(n²) 内存。

第二种解决方案：

第二种解决方案更详细一些，但也遵循通用 LCS 模板。它来自以下重复：

lps(s[i..j]) = 
    s[i] + lps(s[i+1]..[j-1]) + s[j], if s[i] == s[j];
    max(lps(s[i+1..j]), lps(s[i..j-1])) otherwise

计算 lps 长度的伪代码如下：

compute-lps(s, n):

    // palindromes with length 1
    for i = 1 to n:
        c[i, i] = 1
    // palindromes with length up to 2
    for i = 1 to n-1:
        c[i, i+1] = (s[i] == s[i+1]) ? 2 : 1

    // palindromes with length up to j+1
    for j = 2 to n-1:
        for i = 1 to n-i:
            if s[i] == s[i+j]:
                c[i, i+j] = 2 + c[i+1, i+j-1]
            else:
                c[i, i+j] = max( c[i+1, i+j] , c[i, i+j-1] )

如果我想有效地构造lps，它仍然需要 O(n²) 时间和内存（因为我需要桌子上的所有单元格）。分析相关问题，例如 LIS，可以用 LCS 以外的方法解决，用更少的内存（LIS 可以用 O(n) 内存解决），我想知道是否可以用 O(n) 内存解决它，也。

LIS 通过链接候选子序列来实现这个界限，但是对于回文则更难，因为这里重要的不是子序列中的前一个元素，而是第一个元素。有谁知道是否可以做到，或者以前的解决方案内存是最优的吗？

4

2 回答 2

6

这是一个非常节省内存的版本。但我还没有证明它总是 O(n)记忆。（通过预处理步骤，它可以比CPU 更好，尽管是最坏的情况。）O(n2)O(n2)

从最左边的位置开始。对于每个位置，跟踪最远点的表格，在这些点上您可以生成长度为 1、2、3 等的反射子序列。（意味着我们点左侧的子序列被反射到右侧。）对于每个反射的子序列我们存储一个指向子序列下一部分的指针。

当我们以正确的方式工作时，我们从字符串的 RHS 搜索当前元素的任何出现的位置，并尝试使用这些匹配来改进我们之前的边界。完成后，我们查看最长的镜像子序列，我们可以轻松构建最佳回文序列。

让我们考虑一下character。

  1. 我们从我们最好的回文开始是字母“c”，我们的镜像子序列(0, 11)通过字符串末端的对到达。
  2. 接下来考虑位置 1 处的“c”。我们在表格中最好的镜像子序列(length, end, start)是 now [(0, 11, 0), (1, 6, 1)]。（我将省略您需要生成的链接列表以实际找到回文。
  3. 接下来考虑h位置 2。我们不改进 bounds [(0, 11, 0), (1, 6, 1)]。
  4. 接下来考虑a位置 3。我们将边界改进为[(0, 11, 0), (1, 6, 1), (2, 5, 3)]。
  5. 接下来考虑r位置 4。我们将边界改进为[(0, 11, 0), (1, 10, 4), (2, 5, 3)]。（这就是链表有用的地方。

通过列表的其余部分，我们不会改进那组界限。

所以我们最终得到最长的镜像列表的长度为 2。我们将按照链表（我没有在本描述中记录的）找到它ac。由于该列表的末端位于(5, 3)我们可以翻转的位置列表，插入字符4，然后附加列表以获取carac。

通常，它将需要的最大内存是存储最大镜像子序列的所有长度加上存储所述子序列的链表的内存。通常，这将是非常少量的内存。

在经典的内存/CPU 权衡中，您可以及时对列表进行一次预处理，O(n)以生成O(n)特定序列元素出现的数组的大小散列。这可以让您扫描“使用此配对改进镜像子序列”，而无需考虑整个字符串，这通常应该是较长字符串的主要 CPU 节省。

于 2011-05-26T02:19:15.133 回答
3

@Luiz Rodrigo 问题的第一个解决方案是错误的：字符串的最长公共子序列（LCS）及其反向不一定是回文。

示例：对于字符串 CBACB，CAB 是字符串的 LCS 及其反转，显然不是回文。然而，有一种方法可以让它发挥作用。在构建字符串的 LCS 及其反转后，取其左半部分（包括奇数长度字符串的中间字符）并在右侧用反转的左半部分补足它（如果字符串长度为奇数则不包括中间字符）。它显然是一个回文，并且可以简单地证明它是字符串的子序列。

对于上述 LCS，以这种方式构建的回文将是 CAC。

于 2011-06-06T14:50:44.970 回答