algorithm - 寻找内存最少的最长回文子序列

Question

我正在尝试解决来自 Cormem 的 Introduction to Algorithms 3rd edition 的动态规划问题(pg 405) 询问以下内容:

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, civic, racecar, and aibohphobia (fear of palindromes).

Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input character, your algorithm should return carac.

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

第一种解决方案:

字符串的最长回文子序列 (LPS) 就是 Longest Common Subsequence本身及其反面。 (我在解决了另一个要求序列的 Longest Increasing Subsequence 的相关问题后构建了这个解决方案)。由于它只是一个 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²) 的时间和内存(因为我需要 table 上的所有单元格)。分析相关问题，比如LIS，可以用比LCS更小内存的方法解决(LIS is vulbable with O(n) memory)，我想知道是否有可能用O(n)内存解决它，也是。

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

Answer 1

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

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

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

让我们考虑一下 character .

1. 我们从最好的回文开始，即字母“c”，我们的镜像子序列是用 (0, 11) 对达到的。它们在字符串的末端。
2. 接下来考虑位置 1 处的“c”。我们最好的镜像子序列的形式为 (length, end, start)现在[(0, 11, 0), (1, 6, 1)] . (我将省略您需要生成的链表以实际找到回文。
3. 接下来考虑 h在位置 2。我们没有改进界限 [(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。