比较周期性数据的快速方法 [英] Fast way to compare cyclical data

问题描述

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

Suppose I have the data set {A,B,C,D}, of arbitrary type, and I want to compare it to another data set. I want the comparison to be true for {A,B,C,D}, {B,C,D,A}, {C,D,A,B}, and {D,A,B,C}, but not for {A,C,B,D} or any other set that is not ordered similarly. What is a fast way to do this?

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

Storing them in arrays,rotating, and doing comparison that way is an O(n^2) task so that's not very good.

我的第一个直觉是将数据存储为一个像 {A,B,C,D,A,B,C} 这样的集合，然后搜索一个只有 O(n) 的子集.这可以做得更快吗?

My first intuition would be to store the data as a set like {A,B,C,D,A,B,C} and then search for a subset, which is only O(n). Can this be done any faster?

推荐答案

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

There is a fast algorithm for finding the minimum rotation of a string - https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation. So you can store and compare the minimum rotation.

这篇关于比较周期性数据的快速方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！