最长的重复（非重叠）子序列

Question

8

如何找到最长的重复（非重叠）子序列（而不是子字符串）？

限制条件：

字符串 S 由最多 100,000 个小写字母'a'-'z' 组成。

示例：

字符串 hanadswomehanudsiome 中，最长的重复（非重叠）子序列为 handsome。

期望的时间复杂度为 O(|S| log |S|) 或更好（其中 |S| 是字符串 S 的长度）。

- Dewangga Winardi

不，我还是不理解这个算法。 - Dewangga Winardi

2

为什么你认为存在O（N log N）的解决方案？考虑到这与最长公共子序列问题的相似性，这似乎不太可能。 - Paul Hankin

请问您能否提供原始问题的链接（如果有的话），或者请在您的问题中添加更多细节，例如字符串的最大字符数，字符串是否只包含字母等？ - Pham Trung

2

问题陈述中似乎有两种合理的“不重叠”解释：第一种（也是更可能的）是第一次出现必须在第二次开始之前结束。另一种是不重叠意味着只有不相交，但允许可能交织的出现。在子字符串的情况下，这些含义重合。是否有可能第二种解释是指的？ - kcsquared

1

这篇名为“最长串联散列子序列问题的高效算法”的论文，作者是Adrian Kosowski，似乎解决了这个问题。我相信他们猜测O(n^2)是无法改进的。 - גלעד ברקן

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mnistic · Accepted Answer

这个问题用计算机科学的语言来定义，就是找到至少出现两次且不重叠的最长公共分散子序列（LCSS）。

这是计算机科学领域正在进行的研究之一，也是更一般的最长公共子序列问题的一个子问题。从1977年（Hunt-Szymanski算法）到现在，已经提出了各种形式的解决方案。

关于这个问题的最近一篇文章是Russo和Francisco的“Small Longest Tandem Scattered Subsequences”，它声称该算法的时间复杂度为：

O(min{n, ℓ}λ(1 + log(min{λ, ℓ/λ})) + nλ + ℓ)

在哪里：

然而，正如评论中指出的那样，对于约束的输入大小，时间复杂度会崩溃为O（1）。