循环图的对称轴

Question

我必须用c++编写一个程序，它返回循环图中的对称轴数。循环图具有对称轴，当左侧相对顶点或边之间的值是右边值的镜像时。对称轴可以交叉顶点和边。

例如：

​

​

有比O(n^2)更快的方法吗？

Answer 1

N.M.的答案实际上几乎是正确的，但无论如何都不正确。

让我们将其中一个节点称为开始节点，然后调用轴，传递开始节点，即主轴。在某个轴上翻转一个图形等于将它翻转到主轴和旋转上：

​

​

旋转后，主节点可以放置在任何其他节点位置(而且我们始终可以找到当前轴来完成此操作)。

如果我们把我们的图存储为字符串，那么翻转的图由一个反转的字符串周期性地移动0到N-1位置。这些字符串的相等意味着图的相等。显然，这类匹配的数量等于两次重复的图形字符串中出现的反向字符串数：

​

​

所以是的，KMP具有O(N)复杂性。

但是，当str等于反向(Str)时，您应该避免这种情况，因为尽管它们描述的是相同的轴，但匹配将被计算为0和N偏移。因此，您不应该使用str和它本身的级联，而应该使用这种连接的第一个(2*N - 1)字符，以便在任何情况下实现正确的行为。