algorithm - 比较周期性数据的快速方法

Question

假设我有任意类型的数据集 {A,B,C,D}，我想将它与另一个数据集进行比较。我希望 {A,B,C,D}、{B,C,D,A}、{C,D,A,B} 和 {D,A,B,C} 的比较成立，但是不适用于 {A,C,B,D} 或任何其他没有类似排序的集合。什么是快速的方法来做到这一点？

将它们存储在数组中、旋转并以这种方式进行比较是一项 O(n^2) 任务，所以这不是很好。

我的第一直觉是将数据存储为 {A,B,C,D,A,B,C} 这样的集合，然后搜索一个子集，它的复杂度仅为 O(n)。这可以更快地完成吗？

Answer 1

有一种快速算法可以找到字符串的最小旋转 - https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation .所以你可以存储和比较最小旋转。