Lui*_*igo 12 language-agnostic algorithm dynamic-programming palindrome
我试图解决Cormem的算法导论第3版(第405页)中的动态编程问题,该问题如下:
回文是一些字母表上的非空字符串,它向前和向后读取相同的字符串.回文的实例是长度为1的所有字符串,
civic,racecar,和aibohphobia(回文的恐惧).给出一个有效的算法来找到作为给定输入字符串的子序列的最长回文.例如,给定输入
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通过链接候选子序列来实现这一约束,但是对于回文来说,它更难,因为这里重要的不是后续元素,而是第一个元素.有谁知道是否可以这样做,或者以前的解决方案内存是否最佳？
这是一个非常高效的内存版本.但我没有证明它总是 O(n)记忆.(通过预处理步骤,它可以比CPU 更好,但这是最糟糕的情况.)O(n2)O(n2)
从最左边的位置开始.对于每个位置,跟踪最远点的表格,您可以在该表格中生成长度为1,2,3等的反射子序列(意味着我们点左侧的子序列将反映到右侧.)每个反射的子序列我们存储指向子序列的下一部分的指针.
当我们正确地工作时,我们从字符串的RHS搜索当前元素的任何出现的位置,并尝试使用这些匹配来改善我们以前的边界.当我们完成时,我们会看到最长的镜像子序列,我们可以很容易地构建最好的回文.
让我们考虑一下character.
(0, 11)字符串末端的对子一起到达.(length, end, start)现在是表格中最好的镜像子序列[(0, 11, 0), (1, 6, 1)].(我将省略你需要生成的链表,以便真正找到回文.h位置2.我们不改善界限[(0, 11, 0), (1, 6, 1)].a位置3.我们改善了界限[(0, 11, 0), (1, 6, 1), (2, 5, 3)].r位置4.我们改善了界限[(0, 11, 0), (1, 10, 4), (2, 5, 3)].(这是链表有用的地方.通过列表的其余部分,我们不会改进这组边界.
所以我们结束了最长的镜像列表,长度为2.我们将遵循链接列表(我没有在此描述中记录以找到它ac.由于该列表的末尾位于(5, 3)我们可以翻转的位置列表,插入字符4,然后附加列表以获取carac.
通常,它将需要的最大存储器是存储最大镜像子序列的所有长度加上存储器以存储所述子序列的链接列表.通常这将是非常少量的内存.
在经典的内存/ CPU权衡中,您可以对列表进行一次预处理,O(n)以生成O(n)特定序列元素出现位置的数组哈希值.这可以让您扫描"使用此配对改进镜像子序列",而无需考虑整个字符串,对于较长的字符串,这通常应该是CPU的主要节省.