我有一个整数数组列表，其中每个数组都有一些排序的数字在这里，我想找到基于所有数组的整数序列最常见的组合。例如，如果数组列表如下所示
A1 - 1 2 3 5 7 8
A2 - 2 3 5 6 7
A3 - 3 5 7 9
A4 - 1 2 3 7 9
A5 - 3 5 7 10
在这里
{3,5,7} - {A1,A3,A5}
{2,3} - {A1,A2,A4}
所以我们可以把{3,5,7}或{2,3}作为最常见的组合。
现在我使用的算法如下
找出集合与所有其他集合的交集。并存储结果集。如果结果已经存在，则对结果集进行增量。
例如：
找到下面所有的交叉点
A1 intersection A2
A1 intersection A3
A1 intersection A4
A1 intersection A5
A2 intersection A3
A2 intersection A4
A2 intersection A5
A3 intersection A4
A3 intersection A5
A4 intersection A5
这里a1交叉点a3与a3交叉点a5相同，因此set-{3,5,7}引用可以设置为2。
类似地，可以确定每个结果集的出现。
但是该算法需要O（n ^ 2）复杂度。
假设每个集合都被排序，我确信我们可以找到一个更好的算法，其中O（n）复杂度是我无法记录下来的。
有没有人能提出同样的O（n）算法。
最佳答案
如果有一个长度为n的序列，那么它的前缀的长度为n-1，并且发生的频率至少与此相同-退化情况是最常见的字符，它是长度为1的序列，发生的频率至少与任何更长的序列相同你对后缀的最小长度感兴趣吗？
不管怎样，一个想法是把所有的序列串联起来，用不同的整数将它们分开，这些整数在其他地方都没有出现，然后在线性时间内计算出http://en.wikipedia.org/wiki/Suffix_array一次遍历后缀数组应该可以找到任意给定长度的最常见子序列，而且它不应该跨越两个不同数组之间的间隙，因为每个长度n的序列都是唯一的，因为分隔数组的字符是唯一的（另请参见http://en.wikipedia.org/wiki/LCP_array）