c++ - 循環グラフの対称軸

Question

巡回グラフの対称軸の数を返すプログラムを c++ で作成する必要があります。巡回グラフには、左側の反対側の頂点またはエッジ間の値が右側の値の鏡像である場合に対称軸があります。対称軸は、頂点とエッジの両方と交差する場合があります。

例えば：

これをより速く行う方法はありますO(n^2)か？

Answer 1

nmの答えは実際にはほぼ正しいですが、いずれにしてもそうではありません。

ノードの 1 つを開始ノードと呼び、軸を開始ノード、主軸に渡します。いくつかの軸でグラフを反転することは、主軸と回転でグラフを反転することと同じです:

回転後、メインノードは他のノードの場所に配置できます (また、これを行うための現在の軸をいつでも見つけることができます)。

グラフを文字列として保存すると、0 から N-1 位置まで周期的にシフトされた反転文字列によって記述される反転グラフになります。これらの文字列が等しいということは、グラフが等しいということです。明らかに、そのような一致の数は、2 回繰り返されるグラフの文字列で逆文字列が発生する数と同じです。

そうです、KMP は O(N) の複雑さでトリックを行います。

ただし、str が reverse(str) と等しい場合は避ける必要があります。同じ軸を記述しているにもかかわらず、一致は 0 シフトと N シフトの両方でカウントされるためです。したがって、どのような場合でも適切な動作を実現するには、str とそれ自体の連結ではなく、この連結の最初の (2*N – 1) 文字のみを使用する必要があります。