简单压缩方案的最佳运行时间

Question

这是一个简单的谜题，在生物信息学中有一些应用。这是朋友工作中出现的一些抽象版本。

考虑一个非常简单的压缩方案，其输出由两个操作组成：

为了记法方便，put('x')写成字符x，dup()写成*。

例如，"a**b*c" 扩展为 "aaaabaaaabc"。

要压缩给定的字符串s，找到这两个操作的最短列表来生成它。

例如 "aaaaaaaaaab" 缩短为 a**a*b。（a***aab也是可以的，但要长一个字符。）

我的问题是：最佳压缩的最佳可实现运行时间是多少？（实现该运行时的算法是什么。）

我相信线性运行时间是可能的，但我还没有发现任何比二次运行时间更好的东西。（不太担心使用额外的 space。）

Answer 1

是的，线性运行时间对于此压缩方案是可能的。

创建列表dp。此列表的第 i 个元素将对字符串的前 i 个元素进行最佳压缩。

dp[1] = 1
dp[i] = dp[i-1] + 1
if i is even and first i/2 elements of string are equal to second i/2 elements:
    dp[i] = min(dp[i], dp[i/2] + 1)

要检查第一个 i/2 个元素是否等于第二个 i/2 个元素，您可以找到字符串和从索引 i/2 开始的后缀之间的最长公共前缀。如果此前缀的长度大于或等于 i/2，则前 i/2 个元素确实等于第二个 i/2 个元素。

使用修改后的 LCP 阵列可以加快此操作。

首先，为O(n)中的字符串建立一个suffix array。

然后，为O(n)中的后缀数组建一个longest common prefix array。

现在，在后缀数组中找到完整字符串的索引。假设它是 i。现在，从 i 迭代到 LCP 数组的末尾，用目前看到的最小值替换每个值。同样，在 LCP 数组中从 i-1 向下迭代到 0，用目前看到的最小值替换每个值。

完成后，LCP 数组中的每个值代表该后缀的最长公共前缀和完整的字符串，这就是算法所需要的。请注意，这些值是根据排序的后缀而不是后缀在字符串中的位置排序的。不过使用后缀数组映射它相当简单。

Optimal runtime for simple compression scheme