c++ - 循环图中的对称轴

Question

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

例如：

有什么方法可以比这更快O(n^2)吗？

Answer 1

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

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

旋转后，主节点可以放置在任何其他节点位置（我们也总是可以找到当前轴来执行此操作）。

如果我们将图存储为字符串，则由反向字符串描述的翻转图循环移位 0 到 N-1 个位置。这些字符串的相等意味着图形的相等。显然，这样的匹配数等于两次重复图的字符串中反转字符串的出现次数：

所以是的，KMP 用 O(N) 复杂度来解决问题。

但是你应该避免 str 等于 reverse(str) 的情况，因为 match 将同时计算 0 和 N 移位，尽管它们描述了相同的轴。因此，您不应该使用 str 和其自身的串联，而应仅使用此串联的前 (2*N – 1) 个字符来在任何情况下实现正确的行为。