Мне нужно написать программу в C++, которая возвращает число оси симметрии в циклическом графе. Циклический граф имеет ось симметрии, когда значения между противоположными вершинами или ребрами слева являются зеркальным отображением для значений справа. Ось симметрии может пересекаться как с вершинами, так и с ребрами.Ось симметрии в циклическом графе
, например:
Есть ли способ сделать это быстрее, чем O(n^2)?
Ответ на n.m. на самом деле почти правильный, но не в любом случае.
Позволяет называть один из узлов начальным узлом и ось, проходящую начальный узел, основную ось. Подавать график по некоторой оси равно листать его по главной оси и вращения:
После поворота, основной узел может быть размещен на любом другом месте узла (и мы всегда можем найти текущую ось для делая это).
Если мы храним наш график в виде строки, то перевернутый график описывается инвертированной строкой, циклически сдвинутой на 0 по N-1. Равенство этих строк означает равенство графов. Очевидно, что число таких матчей равно числу из происходит от обратной строки в строке на двукратное графа:
Так что да, KMP делает трюк с O (N) сложности.
Но вам следует избегать случая, когда str равно обратному (str), потому что совпадение будет засчитываться как с сдвигами 0, так и с N, несмотря на то, что они описывают одну и ту же ось. Таким образом, вы должны использовать не конкатенацию str и себя, а только первые (2 * N - 1) символы этой конкатенации для достижения правильного поведения в любом случае.
Ну, я думаю, этот вопрос слишком широк для SO или он может не дать конкретного ответа. – sjsam
Кажется, что ваш график также помечен. Это так? –
Да, и он вводится в массив символов. –