查找数组中的所有重复子序列

Question

我不精通算法设计，但在一次面试中被问到了这个问题。我的解决方案很天真，复杂程度很高，但可以在更短的时间内完成。

给定一个整数数组，查找该数组的所有子序列，这些子序列在数组中重复。打印子序列，然后开始索引和结束索引的所有发生。

e.g 1,0,1,9,5,1,9,5,1

在这里它应该打印

1,9,5

3:5 6:8

9,5,1

4:6 7:9

1,9

3:4 6:7

5,1

5:6 8:9

9,5

4:5 7:8

我的解决方案是从Arr[0]开始直到Arr[N/2 -1]，检查它是否重复，然后将结束索引减少1，然后继续检查它是否重复。

谢谢

Answer 1

我想你说的是连续子数组，而不是不一定是连续的子数组。你的解是O(n^3)。您可以使用后缀树，它允许您在O(n)中找到重复子数组。

http://www.geeksforgeeks.org/suffix-tree-application-3-longest-repeated-substring/