找到重复时间最长的子数组
给定一个数组< code>a[0..< code>0之间的整数的N-1]
例：
输入a=[0,1,2,1,4,1,2,2,0,5]
预期输出：重复次数最多：[1,2,1]；尺寸：3
共有2个答案
我相信，这个问题相当于找到最长的重复子串，https://en.wikipedia.org/wiki/Longest_repeated_substring_problem.如果允许重叠子串，则可以在线性时间内使用后缀树有效地解决该问题。然而，在这种情况下，似乎需要识别非重叠子串，这种方法不起作用。至少，它可以使用动态规划在二次时间内解决，https://www.geeksforgeeks.org/longest-repeating-and-non-overlapping-substring/.
众所周知，这类问题有一种幼稚的解决方法——需要花费大量时间，并对所有可能的解决方案进行强力搜索。
显然，你不是在找那个。每当你处于这种情况下，答案总是动态编程。这是一个相当广泛的，对初学者来说很难，但在计算机科学中非常重要。也就是说，我不能回答这个问题。
但这里有一种方法可以解决这个问题。
由于A和B的公共子数组必须从某个A[i]和B[j]开始，因此让dp[i][j]是A[i：]和B[j：]的最长公共前缀。每当A[i]==B[j]，我们就知道dp[i][j]=dp[i 1][j 1] 1。此外，答案是max（dp[i][j]）超过所有i，j。
我们可以执行自下而上的动态规划，以根据这种递归找到答案。我们的循环不变性是，对于任何较大的i，j，答案已经正确计算并存储在dp中。
希望这有帮助。祝你好运。
-
解决此问题的最佳方法（性能方面）是什么？有人建议我使用后缀树。这是最好的方法吗？
-
我正在寻找一种快速算法，搜索给定字符串中最长的重复子字符串（至少重复1次），并尽可能降低时间复杂度和（如果可能）内存（RAM）。 我见过一些实现，但大多数都不是为大量字符设计的（比如说）。一个例子是： 我已经尝试了100次包含的字符串。 它适用于小弦( 编辑：有没有办法不用在内存中加载一个（比如20GB）文件就可以做到这一点？
-
考虑一个问题来寻找区间图的最小支配集。在区间调度的上下文中，它被转换为以下问题： 存在多个可能相互重叠的间隔。找到区间的最小子集，以便对于未包含在子集中的每个区间，它将在与它重叠的子集中找到至少1个区间。 有一个公认的贪婪解决方案可从互联网上的各种来源，例如康奈尔大学的一个解决方案：http://www.cs.cornell.edu/Courses/cs4820/2011sp/handouts/s
-
我知道这是一个有点老生常谈的话题，但我已经达到了从已经得到的答案中得到的帮助的极限。 这是针对Rosalind项目问题LREP的。我试图找到字符串中最长的k-peated子串，我得到了后缀树，这很好。我知道我需要用每个节点的后代叶子数来注释后缀表，然后用
-
最长的重复子串问题如下： 给定一个字符串w，找到至少出现在两个位置的w的最长子串。 这个问题可以在线性时间使用后缀树解决，在线性时间使用增强的后缀数组解决。 我的问题是——对于这个问题，有没有不涉及后缀树或后缀数组的线性时间算法？我很好奇，因为后缀树和后缀数组很难编码和操作，如果有一种算法解决这个问题，而不需要这些其他结构的编码或内存开销，那就太好了。 谢谢
-
问题内容： 我有一个包含2个字段的表：唯一ID，用户ID（外键）和日期时间。这是对服务的访问日志。我在SQL Server中工作，但我希望得到不可知论的答案。 我想使用SQL为最长间隔开始的特定用户查找ID。 因此，举例来说，假设我的值如下（为一位用户简化）： 如果我搜索用户1的最长间隔，我将得到ID 2（也可以在那儿获得间隔的长度，但不那么关键）。 在SQL中最有效的方法是什么？ 注意：ID不一