2

我想检测循环缓冲区是否是相同长度的其他缓冲区列表的镜像或旋转。

例如，给定以下 3 个缓冲区：

AAABCCCA
AABCCBAA
AAAACCAA

Then: CCBAAAAC会匹配，因为它是第一个缓冲区的镜像旋转。

目前我只是比较每次旋转中的每个缓冲区，然后反转缓冲区并再次执行所有操作。

这需要： 2*n*i缓冲区比较。（其中 n 是要比较两个的缓冲区的数量，i 是缓冲区的长度）。

有谁知道更快的算法？

要比较的列表在增长（因为我发现一个不在我拥有的列表中）。有没有一种方法可以让我以某种方式“订购”缓冲区，以便可以更快地进行比较？

我的一个想法是还存储每个缓冲区的排序版本，以便您可以快速比较是否存在相同数量的项目。

但是是否有更通用的解决方案来以某种方式按“循环序列”排序？

4

1 回答 1

3

对于每个缓冲区，您可以旋转它，直到它具有最小的字典值。

例如，您的示例缓冲区可以像这样旋转：

AAABCCCA -> AAAABCCC
AABCCBAA -> AAAABCCB
AAAACCAA -> AAAAAACC

这基本上意味着将价值最低的物品放在第一位。如果有平局，比较下一个项目，等等。这为任何模式提供了唯一的排序。

于 2013-06-13T01:31:19.210 回答