循环图中的对称轴
Axis of symmetry in cyclic graph
我必须用 c++ 编写一个程序，其中 returns 循环图中对称轴的数量。
当左侧相对顶点或边之间的值是右侧值的镜像时，循环图具有对称轴。
对称轴可以同时与顶点和边相交。
例如：
有没有比O(n^2)更快的方法？
n.m.的答案实际上几乎是正确的，但在任何情况下都不是。
让我们将其中一个节点称为起始节点，并将传递起始节点的轴称为主轴。
在某个轴上翻转图形等于在主轴上翻转图形并旋转：
旋转后，主节点可以放在任何其他节点位置（我们也总是可以找到当前轴）。
如果我们将图形存储为字符串，则翻转图形由循环移动 0 到 N-1 个位置的反向字符串描述。
这些字符串的相等性意味着图形的相等性。显然，这种匹配的数量等于两次重复图中字符串中反转字符串的出现次数：
所以是的，KMP 以 O(N) 的复杂度完成了这个技巧。
但是你应该避免 str 等于 reverse(str) 的情况，因为 match 将同时计算 0 和 N 移位，尽管它们描述的是同一个轴。所以，你不应该使用 str 和它本身的连接，而应该只使用这个连接的前 (2*N – 1) 个字符来在任何情况下实现正确的行为。
我必须用 c++ 编写一个程序，其中 returns 循环图中对称轴的数量。 当左侧相对顶点或边之间的值是右侧值的镜像时，循环图具有对称轴。 对称轴可以同时与顶点和边相交。
例如：
有没有比O(n^2)更快的方法？
n.m.的答案实际上几乎是正确的，但在任何情况下都不是。
让我们将其中一个节点称为起始节点，并将传递起始节点的轴称为主轴。 在某个轴上翻转图形等于在主轴上翻转图形并旋转：
旋转后，主节点可以放在任何其他节点位置（我们也总是可以找到当前轴）。
如果我们将图形存储为字符串，则翻转图形由循环移动 0 到 N-1 个位置的反向字符串描述。 这些字符串的相等性意味着图形的相等性。显然，这种匹配的数量等于两次重复图中字符串中反转字符串的出现次数：
所以是的，KMP 以 O(N) 的复杂度完成了这个技巧。
但是你应该避免 str 等于 reverse(str) 的情况，因为 match 将同时计算 0 和 N 移位，尽管它们描述的是同一个轴。所以，你不应该使用 str 和它本身的连接，而应该只使用这个连接的前 (2*N – 1) 个字符来在任何情况下实现正确的行为。